← 返回题目列表

AtCoder · agc011_d

D. 半反射镜

中文机器翻译题面 查看原题

分数: 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 是 A or B.

输入

输入由标准输入按以下格式给出:

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