{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003ePia is getting ready for her flight to the NWERC 2018 in\n Eindhoven. As she is packing her hard drive, she remembers the\n airline’s ridiculous weight restrictions, which may pose a\n problem. You see, the hard drive is essentially a string of\n ones and zeros, and its weight depends on the number of “bit\n changes” in it: for any two adjacent bits storing two different\n values, the hard drive gets slightly heavier, so Pia cannot\n just store arbitrary information on it.\u003c/p\u003e\n \u003cp\u003eTo make matters worse, the drive is so old that some bits\n are already broken and will always store zeros. The first bit\n will never be broken, but the last bit will always be.\u003c/p\u003e\n \u003cp\u003ePia decides to treat this situation as a challenge: she is\n now trying to modify the information on the hard drive so that\n it has exactly the maximum number of bit changes permitted by\n the airline. However, the broken bits make this harder than\n expected, so she needs your help.\u003c/p\u003e\n \u003cp\u003eFind a bit pattern which can be stored on the hard drive and\n has exactly the desired number of bit changes.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne line with three integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\leq n \\leq 5\\cdot 10^5$\u003c/span\u003e,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq c, b \\le\n n-1$\u003c/span\u003e), the size of the hard drive in bits, the\n desired amount of bit changes, and the number of broken\n bits. The positions on the hard drive are numbered from\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eOne line with \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$z_1, \\ldots , z_\n b$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\leq z_1 \u0026lt;\n z_2 \u0026lt; \\ldots \u0026lt; z_ b \u003d n$\u003c/span\u003e), the positions of\n the broken bits on the hard drive.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput a bit string of length \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, representing Pia’s hard drive and\n containing exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e bit\n changes. If there are multiple valid solutions, you may output\n any one of them. It is guaranteed that at least one solution\n exists.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 2 3\n2 3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e00010\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 4 2\n2 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0010110\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}