문제

\texttt{0}$\texttt{0}$과 \texttt{1}$\texttt{1}$로 구성된 길이 N$N$의 이진 수열이 있다. 이러한 이진 수열은 \texttt{0}$\texttt{0}$ 또는 \texttt{1}$\texttt{1}$이 연속적으로 나타난 것을 이어붙인 모양을 하게 되는데, 이처럼 한 문자가 연속적으로 나타나는 것을 체인이라고 한다. 예를 들어 이진 수열 \texttt{1001110000}$\texttt{1001110000}$이 주어지면, 이것은 차례로 길이가 1$1$인 \texttt{1}$\texttt{1}$의 체인, 길이가 2$2$인 \texttt{0}$\texttt{0}$의 체인, 길이가 3$3$인 \texttt{1}$\texttt{1}$의 체인, 그리고 길이가 4$4$인 \texttt{0}$\texttt{0}$의 체인을 이어붙인 모양을 하고 있다. 이진 수열에 포함된 \texttt{1}$\texttt{1}$의 체인의 길이를 차례로 나열한 것을 이 수열의 힌트 수열이라고 한다. 예를 들어 이진 수열 \texttt{1001110000}$\texttt{1001110000}$의 힌트 수열은 \langle {1,\;3} \rangle$\langle {1,\;3} \rangle$이고, 이진 수열 \texttt{01110001111101001}$\texttt{01110001111101001}$의 힌트 수열은 \langle {3,\;5,\;1,\;1} \rangle$\langle {3,\;5,\;1,\;1} \rangle$이다.

당신은 힌트 수열이 주어졌을 때 이를 바탕으로 원래의 이진 수열을 복원하려고 한다. 예를 들어 힌트 수열이 \langle {1,\;2,\;3} \rangle$\langle {1,\;2,\;3} \rangle$이고, N=8$N=8$이라면, 이를 바탕으로 원래의 이진 수열 \texttt{10110111}$\texttt{10110111}$을 복원해 낼 수 있다. 수열을 완전히 복원하진 못하더라도 일부분을 복원할 수 있는 경우도 있다. 예를 들어 힌트 수열이 \langle {3} \rangle$\langle {3} \rangle$이고 N=5$N=5$라면, 가능한 경우는 \texttt{11100}$\texttt{11100}$, \texttt{01110}$\texttt{01110}$, \texttt{00111}$\texttt{00111}$의 세 가지 경우밖에 없다. 이 때에는 어떤 경우라도 가운데 위치에 \texttt{1}$\texttt{1}$이 오기 때문에, 이를 \texttt{??1??}$\texttt{??1??}$로 복원할 수 있다. 여기서 \texttt{?}$\texttt{?}$는 해당 위치를 복원할 수 없었음을 나타낸다.

그러나 경우에 따라서는 수열을 추가적으로 복원하지 못할 수도 있다. 예를 들어 힌트 수열이 \langle {3,\;2} \rangle$\langle {3,\;2} \rangle$이고 N=11$N=11$이라고 하자. 그러면 이를 이진 수열로 복원하는 방법은 \texttt{11100000011}$\texttt{11100000011}$, \texttt{00011101100}$\texttt{00011101100}$, \texttt{11100011000}$\texttt{11100011000}$ 등 여러 가지가 있다. 이처럼 수열의 각 위치에 \texttt{0}$\texttt{0}$이 올 수도 있고 \texttt{1}$\texttt{1}$이 올 수도 있기 때문에, 수열의 어느 위치도 하나로 확정할 수가 없다. 하지만 이진 수열의 일부를 미리 알고 있다면 복원에 도움이 되기도 한다. 예를 들어, 힌트 수열이 \langle {3,\;2} \rangle$\langle {3,\;2} \rangle$이고, N=11$N=11$이며, 수열의 일부가 \texttt{??1?0?0???0}$\texttt{??1?0?0???0}$와 같다고 하자. 여기서 \texttt{?}$\texttt{?}$는 해당 위치를 알 수 없었음을 나타낸다. 이에 맞춰서 복원하는 경우를 모두 따져보면 \texttt{11100001100}$\texttt{11100001100}$, \texttt{11100000110}$\texttt{11100000110}$, \texttt{01110001100}$\texttt{01110001100}$, \texttt{01110000110}$\texttt{01110000110}$ 의 네 가지 경우가 가능하다. 가능한 모든 경우에 대해 한 위치가 동일하게 복원되는 것들을 모두 모아보면, 이 경우에는 이진 수열을 \texttt{?11?000?1?0}$\texttt{?11?000?1?0}$로 복원할 수 있음을 알 수 있다.

N$N$, 힌트 수열, 그리고 이진 수열의 일부가 주어졌을 때, 수열을 복원하는 프로그램을 작성하여라. 주어진 정보로부터 복원 가능한 모든 경우를 따져 보았을 때, 어떤 특정 위치에 한 문자(\texttt{0}$\texttt{0}$ 또는 \texttt{1}$\texttt{1}$)가 모든 경우에 대해 공통적으로 나타난다면, 해당 위치를 해당 문자로 복원할 수 있는 것이다. 만일 주어진 이진 수열에 비해 추가적으로 복원하는 것이 불가능하다면 주어진 이진 수열을 그대로 출력하면 된다. 또한 원래 주어진 정보에 모순이 있다면 복원 가능한 경우가 하나도 존재하지 않을 수 있는데, 이러한 경우에는 \texttt{IMPOSSIBLE}$\texttt{IMPOSSIBLE}$ 을 출력한다. 예를 들어, 힌트 수열이 \langle {3,\;3} \rangle$\langle {3,\;3} \rangle$이고 주어진 이진 수열이 \texttt{??010??}$\texttt{??010??}$이었다면, 여기에 모순되지 않게 수열을 복원할 수는 없다.