In life, there are always things that cannot be perfectly balanced; this is what the saying "you cannot have both fish and bear's paw" refers to. Architect Little X is currently struggling with such a problem in a recent design: for the sake of the living environment, the distance between buildings should be large, but to save land resources, the distance between buildings should be reduced; should a south-facing room be a living room or a bedroom; and so on...

To optimize the design, Little X decided to model the problem by abstracting the choice of parameters into Boolean variables and the various requirements into Boolean expressions. The goal is to choose a parameter setting that satisfies as many requirements as possible, which corresponds to choosing an assignment for the Boolean variables in the model such that as many Boolean expressions as possible are satisfied. Please help Little X set the parameters in the design to make the design as optimal as possible.

The model is formally described as follows. The model contains $n$ Boolean variables $x_1, x_2, \dots, x_n$ and $m$ Boolean expressions $E_1, E_2, \dots, E_m$. An assignment of Boolean variables is a mapping from $\{x_1, x_2, \dots, x_n\}$ to $\{\text{True}, \text{False}\}$. A Boolean expression $E$ is satisfied if the value of the expression is $\text{True}$.

Boolean expressions contain three types of operations: AND ($\&$), OR ($|$), and NOT ($\sim$), which can be defined inductively as follows:

Base: 1) A single Boolean variable $x_i$ forms a Boolean expression $E$. $E$ is satisfied if and only if $x_i$ takes the value $\text{True}$.

Induction: 1) If $E$ is a valid Boolean expression, then $E'=(E)$ is also a Boolean expression. $E'$ is satisfied if and only if $E$ is satisfied. 2) If $E$ is a valid Boolean expression, then $E'=\sim E$ is also a Boolean expression. $E'$ is satisfied if and only if $E$ is not satisfied (i.e., it takes the value $\text{False}$). 3) If $E_1, E_2$ are valid Boolean expressions, then $E'=E_1\&E_2$ is also a Boolean expression. $E'$ is satisfied if and only if both $E_1$ and $E_2$ are satisfied. 4) If $E_1, E_2$ are valid Boolean expressions, then $E'=E_1|E_2$ is also a Boolean expression. $E'$ is satisfied if and only if $E_1$ is satisfied or $E_2$ is satisfied.

All valid Boolean expressions are generated by the above rules. Some examples of valid Boolean expressions are: $x_1\& \sim x_2$, $(x_1\& \sim x_2)|x_3$.

The operator precedence of Boolean expressions from high to low is NOT, AND, OR. For example, the expression $x_1\& \sim x_2|\sim x_3$ is equivalent to $(x_1\&(\sim x_2))|(\sim x_3)$, meaning the NOT operation is calculated first, followed by AND.

In this problem, the goal is to find an assignment such that as many of the given $m$ Boolean expressions as possible are satisfied.

Input

This is an answer-submission problem; all input files opt*.in are already in the directory. For each input file, the first line contains an integer $n$, representing the number of Boolean variables. The second line contains an integer $m$, the number of Boolean expressions. The next $m$ lines each contain a Boolean expression. The expression format is the same as defined above; please refer to the input files (expressions do not contain spaces).

Output

For each input file, you need to provide the corresponding output file in the corresponding directory (the main filename remains the same, with the extension .out). The output file contains $n$ lines, each containing 0 or 1. The $i$-th line represents the assignment for the $i$-th Boolean variable (1 represents an assignment of $\text{True}$, 0 represents an assignment of $\text{False}$).

Examples

Input 1

3
2
x1&x2&x3
~x1|x2

Output 1

1
1
1

Note

In this problem, any output of $n$ lines of 0 or 1 is a valid output. In this example, if the output is:

1
1
1

then both expressions are satisfied; if the output is:

0
1
1

then only the second expression is satisfied; if the output is:

1
0
0

then no expressions are satisfied.

Subtasks

Each test case is scored individually. For each test case, if the output file you provide is invalid, such as incorrect file format or the output solution does not meet the requirements, the test case receives 0 points. Otherwise, let $k$ be the number of expressions satisfied by your output assignment. For different test cases, we have 10 scoring constants $c_1 \le c_2 \le c_3 \le c_4 \le c_5 \le c_6 \le c_7 \le c_8 \le c_9 \le c_{10}$. Your score in this test case depends on the following rules: If $k < c_1$, you get 0 points. If $k \ge c_1$, you get 1 point. If $k \ge c_2$, you get 2 points. If $k \ge c_3$, you get 3 points. If $k \ge c_4$, you get 4 points. If $k \ge c_5$, you get 5 points. If $k \ge c_6$, you get 6 points. If $k \ge c_7$, you get 7 points. If $k \ge c_8$, you get 8 points. If $k \ge c_9$, you get 9 points. If $k \ge c_{10}$, you get 10 points. If multiple conditions are met, the maximum score is taken as the final score.

Interaction

You can use the checker program to check your output. The format is: ./checker TestNo where TestNo is the test case number. For example, if you have obtained the output opt5.out for data 5, you can use the command ./checker 5 to test whether your output is valid.

Note

Please keep the input files *.in and your output files *.out safe and back them up in time to avoid accidental deletion.