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