Binary String Toggle

There is a binary string $S_0$ of length $N$ whose characters are all 0. You apply $U$ toggle operations to it. The $i$-th operation turns $S_{i-1}$ into $S_i$, so once all $U$ operations are done the string is $S_U$.

The $i$-th operation is given as two integers $L_i$ and $R_i$. It flips every character in the range $[L_i, R_i]$. Both ends included, every 1 inside that range becomes 0 and every 0 becomes 1.

Applying all operations gives the strings $S_0, S_1, \dots, S_U$. Write a program that finds the one that comes last in lexicographic order among these $U+1$ strings.

The first line contains $N$ and $U$. ($1 \le N, U \le 100{,}000$)

Each of the next $U$ lines contains $L_i$ and $R_i$. ($1 \le L_i \le R_i \le N$)

On the first line, print the string that comes last in lexicographic order among the $U+1$ strings.

For the example input, the string changes in this order.

• $S_0$ = 0000000000
• $S_1$ = 0000000011
• $S_2$ = 0000011100
• $S_3$ = 0000011111
• $S_4$ = 1111100011
• $S_5$ = 1100000011
• $S_6$ = 1110000011
• $S_7$ = 1101000011
• $S_8$ = 1110111101
• $S_9$ = 1111000001
• $S_{10}$ = 1111001001