Binary String Toggle

Interview

Time limit2sMemory limit512 MB

Summary

Apply U range-toggle operations to an all-zero binary string and print the lexicographically largest string among all U+1 intermediate states.

Level: Medium7 of 10
Topics: Prefix sum, Greedy, Implementation
Solved: No attempts yet

Problem

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.

Input

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$ )

Output

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

Hint

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

Examples4

Example 1

Input

Expected output

1111100011

Example 2
Input
```
1 1
1 1
```
Expected output
```
1
```
Example 3
Input
```
5 1
1 5
```
Expected output
```
11111
```
Example 4
Input
```
5 3
1 1
2 2
3 3
```
Expected output
```
11100
```