산술 부호화

산술 부호화는 메시지를 $0 \leq x < 1$인 실수 $x$로 나타내는 방법이다. 메시지는 대문자 'A'와 'B'로만 이루어져 있다고 하자. 두 글자의 확률은 $p_A$와 $p_B = 1 - p_A$이고, $0 < p_A < 1$이다.

현재 구간 $[a,b)$는 처음에 $[0,1)$로 두고, 글자 하나씩 처리하며 이 구간을 갱신한다. 글자를 부호화하려면 현재 구간을 다음과 같이 두 개의 부분 구간으로 나눈다. $c = a + p_A(b-a)$라 하자. 다음 글자가 'A'이면 $[a,c)$가 현재 구간이 된다. 그렇지 않으면 현재 구간은 $[c,b)$가 된다. 이 과정을 메시지의 각 글자에 대해 반복한다. 마지막 구간이 $[k,\ell)$이면 부호화된 메시지는 $k$로 정한다.

예를 들어 원래 메시지가 "ABAB"이고 $p_A = p_B = 0.5$이면, 알고리즘에서 만나는 구간의 나열은 [ [0,1) \xrightarrow{A} [0, 0.5) \xrightarrow{B} [0.25, 0.5) \xrightarrow{A} [0.25, 0.375) \xrightarrow{B} [0.3125, 0.375). ] 따라서 부호화된 메시지는 0.3125, 즉 이진수로 0.0101이다.

메시지의 길이, 확률, 부호화된 메시지가 주어졌을 때 원래 메시지를 구하시오.

첫째 줄에는 원래 메시지의 길이인 정수 $N$ ($1 \leq N \leq 15$)이 주어진다. 둘째 줄에는 $p_A = \frac{D}{8}$임을 나타내는 정수 $D$ ($1 \leq D \leq 7$)가 주어진다. 셋째 줄에는 부호화된 메시지의 이진수 표현이 주어진다. 부호화된 메시지의 이진수 표현은 "0."으로 시작하고 길이가 $3N+2$ 이하임이 보장된다.

부호화된 메시지는 'A'와 'B'로만 이루어진 길이 $N$의 원래 메시지에서 이 $p_A$ 값을 사용해 나온 것임이 보장된다.

원래 메시지를 출력한다.