A generic circuit.

There is a circuit with $N$ input gates, and $M$ MOOSE gates.

A MOOSE gate computes the negation of the AND of the inputs. That is, it outputs $0$ if both inputs are $1$, otherwise it outputs $1$.

The gates are numbered $1,\dots ,N+M$ starting with the $N$ input gates. Gate number $N+M$ is the output gate.

Each MOOSE gate's input is from two gates with smaller IDs.

At the moment, all inputs have the same value $x$, which is unknown, but can either have the value $0$ or $1$.

You want to change as many of the inputs to fixed values ($0$ or $1$) instead of $x$ as possible so that the output of the circuit (the value of gate $N+M$) is the same as the output before fixing any inputs. That is, if $y_0$ is produced when $x=0$ and $y_1$ is produced when $x=1$, then the fixed circuit should still produce $y_0$ when $x=0$ and $y_1$ when $x=1$. Output one such optimal choice of hard-wiring.

Constraints

For all subtasks:

$1\le N\le {10}^5$

$1\le M\le 2\times {10}^5$

Subtask	Points	Additional Constraints
1	10	$N\le 5$, $M\le 50$
2	30	$N\le 2\times {10}^2$, $M\le 2\times {10}^4$
3	60	No additional constraints.

Input Specification

The first line of input will contain two space-separated integers, $N$ and $M$.

The next line of input will contain $2M$ space-separated integers. The $2i-1^{\text{th}}$ and $2i^{\text{th}}$ integers specify the inputs to gate $N+i$. These integers are guaranteed to be positive and less than $N+i$.

Output Specification

Output a single line with $N$ characters, denoting an optimal assignment. The $i^{\text{th}}$ character can either be 0 (set to false), 1 (set to true), or x (set to $x$). If there are multiple solutions, output any of them.

Sample Input 1

2 1
1 2

Sample Output 1

x1

Sample Input 2

3 6
1 3 1 2 4 5 4 5 7 6 8 8

Sample Output 2

10x

Sample Input 3

4 18
1 1 2 2 5 6 1 2 7 8 9 9 3 3 4 4 11 12 3 4 13 14 15 15 10 10 16 16 17 18 10 16 19 20 21 21

Sample Output 3

0000