索尼娅决定组织一次花卉展览。由于女孩只喜欢玫瑰和百合,所以她决定这次展览只放这两种花。
展览中有$$$n$$$一排鲜花。 Sonya 可以在第 $$$i$$$ 位置放一朵玫瑰或一朵百合。因此,每个 $$$n$$$ 位置都应该包含一朵花:玫瑰或百合。
她知道有 $$$m$$$ 人会参观这个展览。第 $$$i$$$ 位访问者将访问从 $$$l_i$$$ 到 $$$r_i$$$(含)的所有花朵。女孩知道,每一段都有自己的美丽,等于玫瑰的数量和百合的数量的乘积。
索尼娅希望她的展览能被很多人喜欢。这就是为什么她想以这样的方式放置鲜花,使所有部分的美丽之和尽可能最大。
输入
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n, m\leq 10^3$$$) — the number of flowers and visitors respectively.
Each of the next $$$m$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1\leq l_i\leq r_i\leq n$$$), meaning that $$$i$$$-th visitor will visit all flowers from $$$l_i$$$ to $$$r_i$$$ inclusive.
输出
打印 $$$n$$$ 个字符的字符串。如果您想在第 $$$i$$$ 个位置放置玫瑰,则第 $$$i$$$ 个符号应为“0”,如果您想放置百合,则第 $$$i$$$ 个符号应为“1”。
如果有多个答案,请打印其中一个。
示例
输入 #1
5 3 1 3 2 4 2 5
输出 #1
01100
输入 #2
6 3 5 6 1 4 4 6
输出 #2
110010
注意
在第一个示例中,Sonya 可以将玫瑰放在第一、第四和第五位置,将百合放在第二和第三位置;
- 在$$$[1\ldots3]$$$段中,有一朵玫瑰和两朵百合,所以美度等于$$$1\cdot 2=2$$$;
- 在$$$[2\ldots4]$$$段中,有一朵玫瑰和两朵百合,所以美度等于$$$1\cdot 2=2$$$;
- 在$$$[2\ldots5]$$$段中,有两朵玫瑰和两朵百合,所以美丽等于$$$2\cdot 2=4$$$。
总美丽等于$$$2+2+4=8$$$。
In the second example, Sonya can put roses in the third, fourth, and sixth positions, and lilies in the first, second, and fifth positions;
- 在$$$[5\ldots6]$$$段中,有一朵玫瑰和一朵百合,所以美度等于$$$1\cdot 1=1$$$;
- 在$$$[1\ldots4]$$$段中,有两朵玫瑰和两朵百合,所以美度等于$$$2\cdot 2=4$$$;
- 在$$$[4\ldots6]$$$段中,有两朵玫瑰和一朵百合,所以美丽等于$$$2\cdot 1=2$$$。
总美丽等于$$$1+4+2=7$$$。