Problem Description

There are $ N $ Reversi pieces arranged in a row, each with a 0 on the black side and a 1 on the white side, with all pieces initially showing the black side up. Afterward, the operation of flipping all pieces in a certain interval is performed $ Q $ times. Specifically, in the $ i $ -th operation, all pieces from the $ l_i $ -th piece to the $ r_i $ -th piece (inclusive) are flipped.

Determine the final board state.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ l_1 $ $ r_1 $ . . . $ l_Q $ $ r_Q $

• The first line contains two integers $N, Q\ (1 \leq N, Q \leq 200,000)$ representing the number of pieces and the number of operations, separated by spaces.
• The next $ Q $ lines each contain two integers $l_i, r_i\ (1 \leq l_i \leq r_i \leq N)$ representing the range of the $ i $ -th operation, separated by spaces.

Output Format

Output a string $ S $ representing the final board state. The $ i $ -th character of $ S $ should be the number on the upward-facing side of the $ i $ -th piece from the left. Do not forget to add a newline at the end.

Sample Input and Output

Sample Input #1

5 4
1 4
2 5
3 3
1 5

Sample Output #1

01010

Sample Input #2

20 8
1 8
4 13
8 8
3 18
5 20
19 20
2 7
4 9

Sample Output #2

10110000011110000000

Notes/Hints

Partial Points

This problem has partial scoring:

• If you solve the dataset where $1 \leq N, Q \leq 2,000$, you will be awarded $ 60 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 40 $ points, totaling $ 100 $ points.

Sample Explanation 1

• The board starts as 00000.
• After the first operation, the board becomes 11110.
• After the second operation, the board becomes 10001.
• After the third operation, the board becomes 10101.
• After the fourth operation, the board becomes 01010.
• The final board state 01010 is the answer.
• This case satisfies the additional constraints for partial points.

Sample Explanation 2

• This case satisfies the additional constraints for partial points.

见题面 Input 部分

见题面 Output 部分