{"raw_statement":[{"iden":"problem statement","content":"Consider making a string $s$ of length $N$ consisting of `0` and `1`, where $s$ must satisfy $M$ conditions. The $i$\\-th condition is represented by integers $L_i$ and $R_i$ ($1 \\leq L_i < R_i \\leq N$). This means that there should be equal numbers of `0` and `1` between the $L_i$\\-th and $R_i$\\-th characters (inclusive) of $s$.\nFind the lexicographically smallest string $s$ that satisfies all conditions. It can be proved that the Constraints of the problem guarantee the existence of $s$ that satisfies the conditions."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^6$\n*   $1 \\leq M \\leq 200000$\n*   $1 \\leq L_i < R_i \\leq N$\n*   $(R_i-L_i+1) \\equiv 0 \\mod 2$\n*   $(L_i,R_i) \\neq (L_j,R_j)$ ($i \\neq j$)\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_M$ $R_M$"},{"iden":"sample input 1","content":"4 2\n1 2\n3 4"},{"iden":"sample output 1","content":"0101"},{"iden":"sample input 2","content":"6 2\n1 4\n3 6"},{"iden":"sample output 2","content":"001100"},{"iden":"sample input 3","content":"20 10\n6 17\n2 3\n14 19\n5 14\n10 15\n7 20\n10 19\n3 20\n6 9\n7 12"},{"iden":"sample output 3","content":"00100100101101001011"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}