分数: 900 点
问题陈述
高桥有很多奇特的装置。 这些圆柱形装置从左侧和右侧接收球。 每个设备处于两种状态 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从左边算起的第一个设备由 i- 字符串中的第一个字符 S。 根据这种情况,高桥执行了以下操作 K 次:从左侧将一个球放入最左侧的设备中,然后等待球从两端从装置中出来。 在这里,可以证明球总是在有限的时间后从装置中出来。 之后查找每个设备的状态 K 球已加工。
约束
- 1 \leq N \leq 200,000
- 1 \leq K \leq 10^9
- |S|=N
- 中的每个字符 S 是
AorB.
输入
输入由标准输入按以下格式给出:
N K S
输出
打印一个表示每个设备状态的字符串 K 球已加工。 该字符串必须是 N 个字符长,并且 i-第一个字符必须对应于 i从左边算起第一个设备。
示例输入 1
5 1 ABAAA
示例输出 1
BBAAA
在此输入中,我们将一个球从左侧放入最左侧的设备中,然后从同一位置返回。
示例输入 2
5 2 ABAAA
示例输出 2
ABBBA
示例输入 3
4 123456789 AABB
示例输出 3
BABA