{"problem":{"name":"B. Sonya and Exhibition","description":{"content":"Sonya decided to organize an exhibition of flowers. Since the girl likes only roses and lilies, she decided that only these two kinds of flowers should be in this exhibition. There are $n$ flowers in","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1004B"},"statements":[{"statement_type":"Markdown","content":"Sonya decided to organize an exhibition of flowers. Since the girl likes only roses and lilies, she decided that only these two kinds of flowers should be in this exhibition.\n\nThere are $n$ flowers in a row in the exhibition. Sonya can put either a rose or a lily in the $i$\\-th position. Thus each of $n$ positions should contain exactly one flower: a rose or a lily.\n\nShe knows that exactly $m$ people will visit this exhibition. The $i$\\-th visitor will visit all flowers from $l_i$ to $r_i$ inclusive. The girl knows that each segment has its own _beauty_ that is equal to the product of the number of roses and the number of lilies.\n\nSonya wants her exhibition to be liked by a lot of people. That is why she wants to put the flowers in such way that the sum of _beauties_ of all segments would be maximum possible.\n\n## Input\n\nThe first line contains two integers $n$ and $m$ ($1\\leq n, m\\leq 10^3$) — the number of flowers and visitors respectively.\n\nEach 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\n## Output\n\nPrint the string of $n$ characters. The $i$\\-th symbol should be «_0_» if you want to put a rose in the $i$\\-th position, otherwise «_1_» if you want to put a lily.\n\nIf there are multiple answers, print any.\n\n[samples]\n\n## Note\n\nIn the first example, Sonya can put roses in the first, fourth, and fifth positions, and lilies in the second and third positions;\n\n*   in the segment $[1\\ldots3]$, there are one rose and two lilies, so the _beauty_ is equal to $1\\cdot 2=2$;\n*   in the segment $[2\\ldots4]$, there are one rose and two lilies, so the _beauty_ is equal to $1\\cdot 2=2$;\n*   in the segment $[2\\ldots5]$, there are two roses and two lilies, so the _beauty_ is equal to $2\\cdot 2=4$.\n\nThe total _beauty_ is equal to $2+2+4=8$.\n\nIn the second example, Sonya can put roses in the third, fourth, and sixth positions, and lilies in the first, second, and fifth positions;\n\n*   in the segment $[5\\ldots6]$, there are one rose and one lily, so the _beauty_ is equal to $1\\cdot 1=1$;\n*   in the segment $[1\\ldots4]$, there are two roses and two lilies, so the _beauty_ is equal to $2\\cdot 2=4$;\n*   in the segment $[4\\ldots6]$, there are two roses and one lily, so the _beauty_ is equal to $2\\cdot 1=2$.\n\nThe total _beauty_ is equal to $1+4+2=7$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"索尼娅决定举办一场花卉展览。由于她只喜欢玫瑰和百合，她决定展览中只包含这两种花。\n\n展览中有 $n$ 朵花排成一排。索尼娅可以在第 $i$ 个位置放置一朵玫瑰或一朵百合。因此，每个位置都必须恰好包含一朵花：玫瑰或百合。\n\n她知道恰好有 $m$ 位访客会参观这次展览。第 $i$ 位访客会参观从 $l_i$ 到 $r_i$（包含两端）的所有花。女孩知道每个区间都有其独特的“美丽值”，等于玫瑰数量与百合数量的乘积。\n\n索尼娅希望她的展览受到许多人的喜爱。因此，她希望以一种方式摆放花朵，使得所有区间的“美丽值”之和尽可能大。\n\n第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 10^3$）——分别表示花的数量和访客的数量。\n\n接下来的 $m$ 行每行包含两个整数 $l_i$ 和 $r_i$（$1 lt.eq l_i lt.eq r_i lt.eq n$），表示第 $i$ 位访客会参观从 $l_i$ 到 $r_i$（包含两端）的所有花。\n\n请输出一个长度为 $n$ 的字符串。第 $i$ 个字符应为 «_0_»，表示在第 $i$ 个位置放置玫瑰；否则为 «_1_»，表示放置百合。\n\n如果有多个答案，输出任意一个即可。\n\n在第一个例子中，索尼娅可以在第一、第四和第五个位置放置玫瑰，在第二和第三个位置放置百合；\n\n总“美丽值”为 $2 + 2 + 4 = 8$。\n\n在第二个例子中，索尼娅可以在第三、第四和第六个位置放置玫瑰，在第一、第二和第五个位置放置百合；\n\n总“美丽值”为 $1 + 4 + 2 = 7$。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 10^3$）——分别表示花的数量和访客的数量。接下来的 $m$ 行每行包含两个整数 $l_i$ 和 $r_i$（$1 lt.eq l_i lt.eq r_i lt.eq n$），表示第 $i$ 位访客会参观从 $l_i$ 到 $r_i$（包含两端）的所有花。\n\n## Output\n\n请输出一个长度为 $n$ 的字符串。第 $i$ 个字符应为 «_0_»，表示在第 $i$ 个位置放置玫瑰；否则为 «_1_»，表示放置百合。如果有多个答案，输出任意一个即可。\n\n[samples]\n\n## Note\n\n在第一个例子中，索尼娅可以在第一、第四和第五个位置放置玫瑰，在第二和第三个位置放置百合；在区间 $[ 1 dots.h 3 ]$ 中，有一朵玫瑰和两朵百合，因此“美丽值”为 $1 dot.op 2 = 2$；在区间 $[ 2 dots.h 4 ]$ 中，有一朵玫瑰和两朵百合，因此“美丽值”为 $1 dot.op 2 = 2$；在区间 $[ 2 dots.h 5 ]$ 中，有两朵玫瑰和两朵百合，因此“美丽值”为 $2 dot.op 2 = 4$。总“美丽值”为 $2 + 2 + 4 = 8$。\n\n在第二个例子中，索尼娅可以在第三、第四和第六个位置放置玫瑰，在第一、第二和第五个位置放置百合；在区间 $[ 5 dots.h 6 ]$ 中，有一朵玫瑰和一朵百合，因此“美丽值”为 $1 dot.op 1 = 1$；在区间 $[ 1 dots.h 4 ]$ 中，有两朵玫瑰和两朵百合，因此“美丽值”为 $2 dot.op 2 = 4$；在区间 $[ 4 dots.h 6 ]$ 中，有两朵玫瑰和一朵百合，因此“美丽值”为 $2 dot.op 1 = 2$。总“美丽值”为 $1 + 4 + 2 = 7$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of flowers and visitors, respectively.  \nLet $ S = (s_1, s_2, \\dots, s_n) \\in \\{0,1\\}^n $ be the configuration of flowers, where $ s_i = 0 $ represents a rose and $ s_i = 1 $ represents a lily at position $ i $.  \nLet $ \\mathcal{I} = \\{(l_i, r_i) \\mid i \\in \\{1, \\dots, m\\}\\} $ be the set of visitor intervals, with $ 1 \\leq l_i \\leq r_i \\leq n $.\n\nFor a segment $ (l, r) $, define:  \n- $ R(l,r) = \\sum_{j=l}^{r} (1 - s_j) $: number of roses in $ [l, r] $,  \n- $ L(l,r) = \\sum_{j=l}^{r} s_j $: number of lilies in $ [l, r] $.  \nThe beauty of segment $ (l, r) $ is $ B(l,r) = R(l,r) \\cdot L(l,r) $.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 10^3 $  \n2. For all $ i \\in \\{1, \\dots, m\\} $: $ 1 \\leq l_i \\leq r_i \\leq n $\n\n**Objective**  \nMaximize the total beauty:  \n$$\n\\sum_{(l_i, r_i) \\in \\mathcal{I}} B(l_i, r_i) = \\sum_{(l_i, r_i) \\in \\mathcal{I}} \\left( \\sum_{j=l_i}^{r_i} (1 - s_j) \\right) \\left( \\sum_{j=l_i}^{r_i} s_j \\right)\n$$  \nOutput any configuration $ S \\in \\{0,1\\}^n $ achieving the maximum.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1004B","tags":["constructive algorithms","greedy","implementation","math"],"sample_group":[["5 3\n1 3\n2 4\n2 5","01100"],["6 3\n5 6\n1 4\n4 6","110010"]],"created_at":"2026-03-03 11:00:39"}}