算术编码是一种将消息表示为实数 $x$（满足 $0 \le x < 1$）的方法。我们假设消息仅由大写字母“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 \le N \le 15$)，即原始消息的长度。第二行包含整数 $D$ ($1 \le D \le 7$)，表示 $p_A = \frac{D}{8}$。第三行包含编码后消息的二进制表示。保证编码后消息的二进制表示以“0.”开头，且最多包含 $3N + 2$ 个字符。

保证编码后的消息是由长度为 $N$、仅由“A”和“B”组成的消息使用该 $p_A$ 值编码得到的。

输出格式

输出原始消息。

样例

样例输入 1

4
4
0.0101

样例输出 1

ABAB

样例输入 2

6
5
0.100100100100101

样例输出 2

ABBABA