问题描述

有 $N$ 个黑面上写着 0，白面上写着 1 的黑白棋子排成一行，每个棋子都是黑面朝上。然后，对某个区间内的棋子进行了 $Q$ 次翻转操作。具体而言，在第 $i$ 次操作中，从第 $l_i$ 个棋子到第 $r_i$ 个棋子之间的所有棋子都被翻转。

请计算最终的棋盘状态。

输入

输入以以下格式从标准输入中给出。

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

• 第一行包含两个整数 $N$ 和 $Q$，分别表示棋子数和操作次数 $(1≦N,Q≦200,000)$。
• 接下来的 $Q$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 次操作的范围 $(1≦l_i≦r_i≦N)$。

输出

输出一个字符串 $S$，表示最终的棋盘状态。将其打印在一行上。字符串 $S$ 的第 $i$ 个字符表示第 $i$ 个棋子上的数字。注意不要忘记换行。

部分分

本问题设有部分分。

• 对于满足 $1≦N,Q≦2,000$ 的数据集，可以获得 60 分。
• 对于没有额外限制的数据集，只要正确解答，可以额外获得 40 分，总计可得 100 分。

输入示例 1

5 4
1 4
2 5
3 3
1 5

输出示例 1

01010

• 初始棋盘为 00000。
• 第一次操作后，棋盘变为 11110。
• 第二次操作后，棋盘变为 10001。
• 第三次操作后，棋盘变为 10101。
• 第四次操作后，棋盘变为 01010。
• 最终的棋盘状态为 01010。
• 该示例满足部分分的额外限制。

输入示例 2

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

输出示例 2

10110000011110000000

• 该示例满足部分分的额外限制。