题目描述

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

请在所有满足条件的 $s$ 中找出字典序最小的那个。可以证明，在问题的约束下，满足条件的 $s$ 一定存在。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

输出答案。

样例 1

输入

4 2
1 2
3 4

输出

0101

样例 2

输入

6 2
1 4
3 6

输出

001100

样例 3

输入

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

输出

00100100101101001011

说明/提示

约束条件

• $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 \pmod{2}$
• $(L_i, R_i) \neq (L_j, R_j)$（$i \neq j$）
• 输入中的所有值均为整数

翻译由 DeepSeek R1 完成