Problem A
Almost Balanced

Consider making a string $s$ of $\textbf{even}$ length $n$ consisting of $0$ and $1$, where $s$ must satisfy $m$ conditions. The $i^{th}$ condition is represented by integers $T_ i, L_ i, R_ i (1 \leq L_ i<R_ i \leq n), V_ i (0 \leq V_ i)$. Note that $L_ i \not\equiv R_ i \text {(mod 2)}$, or equivalently there is an $\textbf{even}$ number of elements within each range.

If $T_ i = 0$, This means that there are at most $V_ i$ more $0$s than $1$s in the $L_ i^{th}$ and $R_ i^{th}$ characters (inclusive) of $s$.

If $T_ i = 1$, This means that there are at most $V_ i$ more $1$s than $0$s in the $L_ i^{th}$ and $R_ i^{th}$ characters (inclusive) of $s$.

Find the lexicographically smallest string $s$ that satisfies all conditions. It can be proved that the constraints of the problem guarantee the existence of $s$ that satisfies the conditions.

Input

The first line contains two integers $n$ and $m$ $(2\leq n\leq 300\, 000; 1\leq m\leq 300\, 000)$ — the length of the string and the number of conditions. Note once again that $n$ is $\textbf{even}$.

The $i^{th}$ of the following $m$ lines contains four integers $T_ i \in \{ 0,1\} , L_ i, R_ i (1 \leq L_ i < R_ i \leq n), V_ i (0\leq V_ i \leq R_ i - L_ i + 1)$. Note that $L_ i \not\equiv R_ i \text {(mod 2)}$.

Output

Print the lexicographically smallest string $s$ satisfying the conditions.

6 2
0 1 6 2
1 5 6 1

000101

6 3
0 1 6 0
0 1 4 0
1 3 4 0

010101