题目描述

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$

输出格式

答えを出力せよ．

题目大意

你需要构造一个长度为 $n$ 、由 $01$ 组成的字符串，同时需要满足 $m$ 个条件。第 $i$ 个条件由两个整数 $l_i,\ r_i$ 给出，表示字符串位于 $[l_i,r_i]$ 区间的字符必须是相同数量的 $0$ 和 $1$。

请输出满足所有条件且字典序最小的字符串。可以证明在题设条件下总存在至少一个字符串满足所有条件。

$2\le n\le 10^6,\ 1\le m\le 2\times 10^5,\ 1\le l_i< r_i\le n, (r_i - l_i + 1) \bmod 2,\ (l_i,r_i)\neq(l_j,r_j) (i != j)$

4 2
1 2
3 4

0101

6 2
1 4
3 6

001100

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\ \mod\ 2$
• $(L_i,R_i)\ \neq\ (L_j,R_j)$ ($i\ \neq\ j$)
• 入力される値はすべて整数である