← 返回题目列表

Codeforces · 1004/B

B. 索尼娅和展览

中文机器翻译题面 查看原题

索尼娅决定组织一次花卉展览。由于女孩只喜欢玫瑰和百合,所以她决定这次展览只放这两种花。

展览中有$$$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$$$。