CF1004B Sonya and Exhibition

Sonya 决定举办一场花展。由于她只喜欢玫瑰和百合，所以她决定展览中只放这两种花。 展览中有 $n$ 朵花排成一排。Sonya 可以在第 $i$ 个位置放一朵玫瑰或一朵百合。因此，每个位置都必须恰好放一朵花：要么是玫瑰，要么是百合。 她知道将会有 $m$ 位观众参观这场展览。第 $i$ 位观众会参观从 $l_i$ 到 $r_i$（包含两端）的所有花。Sonya 知道，每个区间的美丽值等于该区间内玫瑰数量与百合数量的乘积。 Sonya 希望她的展览能让尽可能多的人喜欢。因此，她想要安排花的摆放方式，使得所有区间的美丽值之和最大。

第一行包含两个整数 $n$ 和 $m$（$1\leq n, m\leq 10^3$），分别表示花的数量和观众的数量。 接下来的 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1\leq l_i\leq r_i\leq n$），表示第 $i$ 位观众会参观从 $l_i$ 到 $r_i$ 的所有花。

输出一个长度为 $n$ 的字符串。第 $i$ 个字符为「0」表示在第 $i$ 个位置放一朵玫瑰，为「1」表示放一朵百合。 如果有多种方案，输出任意一种即可。

在第一个样例中，Sonya 可以在第 1、4、5 个位置放玫瑰，在第 2、3 个位置放百合： - 在区间 $[1\ldots3]$ 中，有 1 朵玫瑰和 2 朵百合，美丽值为 $1\cdot 2=2$； - 在区间 $[2\ldots4]$ 中，有 1 朵玫瑰和 2 朵百合，美丽值为 $1\cdot 2=2$； - 在区间 $[2\ldots5]$ 中，有 2 朵玫瑰和 2 朵百合，美丽值为 $2\cdot 2=4$。 总美丽值为 $2+2+4=8$。 在第二个样例中，Sonya 可以在第 3、4、6 个位置放玫瑰，在第 1、2、5 个位置放百合： - 在区间 $[5\ldots6]$ 中，有 1 朵玫瑰和 1 朵百合，美丽值为 $1\cdot 1=1$； - 在区间 $[1\ldots4]$ 中，有 2 朵玫瑰和 2 朵百合，美丽值为 $2\cdot 2=4$； - 在区间 $[4\ldots6]$ 中，有 2 朵玫瑰和 1 朵百合，美丽值为 $2\cdot 1=2$。 总美丽值为 $1+4+2=7$。 由 ChatGPT 4.1 翻译