D - Half Reflector 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 900 点

問題文

高橋君は，ある特殊な装置をたくさん持っています． この装置は筒状で，左右からボールを入れることができます． また，この装置には 2 種類の状態 A, B があります． 各状態について，装置にボールを入れたときの動作は次のようになっています．

  • 状態 A の装置にボールを入れると，入れた側と同じ側からボールが飛び出してきて，その後すぐに装置の状態は B に変化します．
  • 状態 B の装置にボールを入れると，入れた側と反対側からボールが飛び出してきて，その後すぐに装置の状態は A に変化します．

装置の状態の変化はとても速いので，1 つの装置にボールを入れた後，次にボールが入ってくるまでの間には必ず状態の変化は終わっています．

高橋君は，この装置を N 個つなげたものを作りました．つまり，

  • 左から i (1 \leq i \leq N-1) 番目の装置の右端から飛び出したボールは，すぐに左から i+1 番目の装置に左端から入ります．
  • 左から i (2 \leq i \leq N) 番目の装置の左端から飛び出したボールは，すぐに左から i-1 番目の装置に右端から入ります．

左から i 番目の装置の最初の状態は，文字列 S の i 番目の文字で表されます． 次に高橋君は，一番左の装置の左端からボールを入れ，ボールがどちらかの端から出てくるまで待つということを K 回行いました． ここで，ボールがいつまで経っても出てこないということは起きないことが証明できます． K 回ボールを入れた後の各装置の状態を求めてください．

制約

  • 1 \leq N \leq 200,000
  • 1 \leq K \leq 10^9
  • |S|=N
  • S の各文字は A または 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

Score : 900 points

Problem Statement

Takahashi has a lot of peculiar devices. These cylindrical devices receive balls from left and right. Each device is in one of the two states A and B, and for each state, the device operates as follows:

  • When a device in state A receives a ball from either side (left or right), the device throws out the ball from the same side, then immediately goes into state B.
  • When a device in state B receives a ball from either side, the device throws out the ball from the other side, then immediately goes into state A.

The transition of the state of a device happens momentarily and always completes before it receives another ball.

Takahashi built a contraption by concatenating N of these devices. In this contraption,

  • A ball that was thrown out from the right side of the i-th device from the left (1 \leq i \leq N-1) immediately enters the (i+1)-th device from the left side.
  • A ball that was thrown out from the left side of the i-th device from the left (2 \leq i \leq N) immediately enters the (i-1)-th device from the right side.

The initial state of the i-th device from the left is represented by the i-th character in a string S. From this situation, Takahashi performed the following K times: put a ball into the leftmost device from the left side, then wait until the ball comes out of the contraption from either end. Here, it can be proved that the ball always comes out of the contraption after a finite time. Find the state of each device after K balls are processed.

Constraints

  • 1 \leq N \leq 200,000
  • 1 \leq K \leq 10^9
  • |S|=N
  • Each character in S is either A or B.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print a string that represents the state of each device after K balls are processed. The string must be N characters long, and the i-th character must correspond to the state of the i-th device from the left.

Sample Input 1

5 1
ABAAA

Sample Output 1

BBAAA

In this input, we put a ball into the leftmost device from the left side, then it is returned from the same place.

Sample Input 2

5 2
ABAAA

Sample Output 2

ABBBA

Sample Input 3

4 123456789
AABB

Sample Output 3

BABA