Felicia Day loves playing DnD. For this, she needs various dice, in this case $N$-sided ones. She likes risk, and to save some money, she bought $K$ dice on sale. However, she discovered that not all of them are fair (a die is fair if the probability of landing on each of its sides is equal). More precisely, each die is fair with probability $P$, and if it is not fair, the probabilities for each of its sides are generated in the following way:

1. For $i$ from 1 to $N$, we generate a random number between 0 and 1, which we call $Q_i$.
2. The probability of landing on side $i$ is equal to $\frac{Q_i}{Q_1 + Q_2 + \dots + Q_N}$.

We can think of fair dice as those with equal values of $Q_i$.

Felicia is in a hurry to figure out which ones are fair and which are not, but she doesn't have much time, so she has rolled each die $M$ times. She has recorded the results – how many times each of the sides has landed for each of the dice, but she is not sure how to analyze this data. Help her by writing a program that classifies the dice as fair or unfair. Of course, 100% accuracy is not expected. Instead, there is a penalty for each error: if you classify a fair die as unfair, the penalty is $X$, and if you classify an unfair die as fair, it is $Y$. Your goal is to minimize your total penalty for errors.

Constraints

• $2 \le N \le 8$
• $15 \le M \le 40$
• $0.5 \le P \le 0.8$
• $0.3 \le X, Y \le 0.7$
• $X + Y = 1$
• $K = 100000$

Input

From the first line of standard input, $N, M, P, X$ and $Y$ are read. The next line contains $K$. On each of the following $K$ lines, $N$ numbers are entered – on line $i$, the $j$-th number is the number of times side $j$ has landed on die $i$.

Output

On standard output, for each die, print '1' on a separate line to classify it as fair, or '0' for unfair.

Subtasks

Each test is evaluated separately. The points for a given test are determined as follows:

1. Let $TP$ be the total penalty from errors of your solution.
2. $AP = \frac{TP}{K}$
3. $BAP = \min(P \times X, (1 - P) \times Y)$
4. $S = \max\left(\frac{BAP - AP}{BAP}, 0\right)$
5. $R = \frac{S}{S_{Author}}$
6. Your points are: $$ \begin{cases} 0.3 + 0.7 \times \left(1 - \left(1 - \frac{R - 0.8}{1 - 0.8}\right)^{0.75}\right) & \text{if } R \ge 0.8 \\ \frac{0.3}{0.8} \times R & \text{if } R < 0.8 \end{cases} $$

Examples

Input 1

3 15 0.6 0.35 0.65
4
4 7 4
5 5 5
9 5 1
3 6 6

Output 1

0
1
0
1

Note

It turns out that the solution correctly identifies dice 2 and 3, but incorrectly identifies 1 and 4. The first error carries a penalty of 0.35, and the second 0.65. The total penalty is 1.0.