[AGC056C] 01 Balanced

你需要构造一个长度为 $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)$

[problemUrl]: https://atcoder.jp/contests/agc056/tasks/agc056_c `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 $

答えを出力せよ．

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 $) - 入力される値はすべて整数である