하드 드라이브

Pia는 Eindhoven에서 열리는 NWERC 2018에 참가하기 위해 비행기를 탈 준비를 하고 있다. 하드 드라이브를 짐에 넣으려다, 항공사의 터무니없는 무게 제한이 문제가 될 수 있다는 사실을 떠올린다. 하드 드라이브는 사실상 0과 1로 이루어진 문자열이고, 무게는 비트 변화의 횟수에 달려 있다. 인접한 두 비트가 서로 다른 값을 저장하면 하드 드라이브는 조금 무거워지므로, Pia는 아무 정보나 마음대로 저장할 수 없다.

설상가상으로 드라이브가 너무 오래되어 일부 비트는 이미 고장 나서 항상 0을 저장한다. 첫 번째 비트는 절대 고장 나지 않지만, 마지막 비트는 항상 고장 나 있다.

Pia는 이 상황을 도전 과제로 삼기로 한다. 그녀는 이제 항공사가 허용하는 최대 비트 변화 횟수를 정확히 갖도록 하드 드라이브의 정보를 수정하려고 한다. 하지만 고장 난 비트 때문에 예상보다 어려워졌으므로, 그녀는 여러분의 도움이 필요하다.

하드 드라이브에 저장할 수 있으면서 정확히 원하는 비트 변화 횟수를 갖는 비트 패턴을 찾아라.

입력은 다음과 같다.

• 세 정수 n, c, b가 주어지는 한 줄 (2 ≤ n ≤ 5 · 10^5, 1 ≤ c, b ≤ n − 1). n은 하드 드라이브의 비트 단위 크기, c는 원하는 비트 변화 횟수, b는 고장 난 비트의 개수이다. 하드 드라이브의 위치는 1부터 n까지 번호가 매겨진다.
• b개의 정수 z1, . . . , zb가 주어지는 한 줄 (2 ≤ z1 < z2 < . . . < zb = n). 고장 난 비트의 위치이다.

Pia의 하드 드라이브를 나타내며 정확히 c번의 비트 변화를 포함하는, 길이 n의 비트 문자열을 출력한다. 유효한 답이 여러 개라면 그중 아무거나 출력해도 된다. 답이 적어도 하나 존재함이 보장된다.