题目描述

高桥君有很多特殊装置。这种装置呈筒状，可以从左右两端放入球。该装置有两种状态 A 和 B。对于每种状态，将球放入装置时的行为如下：

• 当装置处于状态 A 时，将球从某一侧放入后，球会从同一侧弹出，之后装置立即变为状态 B。
• 当装置处于状态 B 时，将球从某一侧放入后，球会从对侧弹出，之后装置立即变为状态 A。

装置的状态变化非常快，保证对同一个装置连续放球之间，状态变化一定已经完成。

高桥君将这样 $N$ 个装置串联在一起。具体地：

• 从左起第 $i$ 个装置（$1\leq i\leq N-1$）的右端弹出的球会立即从第 $i+1$ 个装置的左端进入。
• 从左起第 $i$ 个装置（$2\leq i\leq N$）的左端弹出的球会立即从第 $i-1$ 个装置的右端进入。

左起第 $i$ 个装置的初始状态由字符串 $S$ 的第 $i$ 个字符表示。接下来，高桥君要进行 $K$ 次操作，每次都从最左侧装置的左端放入一个球，然后等待球从某个端口弹出。可以证明，球最终一定会从装置的一侧弹出，不会永远卡住。请你求出，进行 $K$ 次操作后，每个装置的状态，并用一个字符串输出。

输入格式

输入以以下格式从标准输入读入：

$N\ K\ S$

输出格式

请输出进行 $K$ 次操作后，各个装置的状态所组成的字符串。字符串长度为 $N$，第 $i$ 个字符表示左起第 $i$ 个装置的状态。

样例 1

输入

5 1
ABAAA

输出

BBAAA

样例 2

输入

5 2
ABAAA

输出

ABBBA

样例 3

输入

4 123456789
AABB

输出

BABA

说明/提示

限制条件

• $1\leq N\leq 200,\!000$
• $1\leq K\leq 10^9$
• $|S|=N$
• $S$ 的每个字符为 A 或 B

样例解释 1

在这个输入中，从最左侧装置的左端放入球后，球会从原处弹出。

由 ChatGPT 5 翻译