题目描述

考虑构造一个长度为$N$的字符串$s$，由0和1组成，其中$s$必须满足$M$个条件。第$i$个条件由整数$L_i$和$R_i$表示，($1 \leq L_i < R_i \leq N$)。这意味着在字符串$s$的第$L_i$个字符和第$R_i$个字符（包括）之间应该有相等数量的0和1。

找到满足所有条件的字典序最小的字符串$s$。可以证明问题的约束条件保证了存在满足条件的$s$。

约束条件

• $2 \leq N \leq 10^6$
• $1 \leq M \leq 200000$
• $1 \leq L_i < R_i \leq N$
• $(R_i-L_i+1) \equiv 0 \mod 2$
• $(L_i,R_i) \neq (L_j,R_j)$ ($i \neq j$)
• 输入中的所有值都是整数。

输入

从标准输入读入数据，数据格式如下：

$N$ $M$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_M$ $R_M$

输出

打印答案。

示例输入 1

4 2
1 2
3 4

示例输出 1

0101

示例输入 2

6 2
1 4
3 6

示例输出 2

001100

示例输入 3

20 10
6 17
2 3
14 19
5 14
10 15
7 20
10 19
3 20
6 9
7 12

示例输出 3

00100100101101001011