P16991 [NWERC 2018] Hard Drive

Pia is getting ready for her flight to the NWERC 2018 in Eindhoven. As she is packing her hard drive, she remembers the airline's ridiculous weight restrictions, which may pose a problem. The hard drive is essentially a string of ones and zeros, and its weight depends on the number of “bit changes” in it: for any two adjacent bits storing two different values, the hard drive gets slightly heavier. To make matters worse, the drive is so old that some bits are already broken and will always store zeros. The first bit will never be broken, but the last bit will always be. Pia is now trying to modify the information on the hard drive so that it has exactly the maximum number of bit changes permitted by the airline. Find a bit pattern which can be stored on the hard drive and has exactly the desired number of bit changes.

The input consists of: - One line with three integers $n,c,b$ ($2\le n\le 5\cdot10^5$, $1\le c,b\le n-1$), the size of the hard drive in bits, the desired amount of bit changes, and the number of broken bits. - One line with $b$ integers $z_1,\ldots,z_b$ ($2\le z_1

Output a bit string of length $n$, representing Pia's hard drive and containing exactly $c$ bit changes. If there are multiple valid solutions, you may output any one of them. It is guaranteed that at least one solution exists.