ゲーム「Zuma」の作成

あなたはゲーム「Zuma」を作ることにしました。現在取り組んでいるのは、同じ色のボール同士が衝突したときに、その部分を取り除く処理です。つまり、さまざまな色のボールが並んでいるリストに対して、プレイヤーがある色のボールを指定の位置に撃ち込みます。その結果、撃ち込んだボールも含めて同じ色のボールが3個以上連続した場合、そのまとまりが消えて、両端のボールが隙間を埋めるように詰められます。

もしも3個以上のボールが引き続き衝突し、同じ色で固まっている場合は、そのまとまりも同様に消えます。この処理は、衝突しているボールの色が違うものになるか、ボールがすべてなくなるまで繰り返されます。

Input

最初の行には、文字列 b (1 ≤ |b| ≤ ) が与えられ、これはボールが並んでいる様子を表します。ボールの色は、小文字のラテン文字（y は黄、b は青、r は赤など）で表されます。

次の行には、ユーザーがボールを撃ち込む場所を示すインデックス i (1 ≤ i ≤ |b|) と、撃ち込むボールの色 c（小文字のラテン文字）が与えられます。

Output

プログラムは、最終的に残ったボールの並びを出力してください。

Examples

Input	Output
rrryyrrb 4 y	b
rgbbrg 3 b	rgrg
ggrrrbbb 1 g	rrrbbb
gbyw 1 y	ygbyw
cabbbacc 4 b	caacc

Explanation

rrryyrrb → rrryyyrrb → rrrrrb → b

rgbbrg → rgbbrg → rgrg

ggrrrbbb → gggrrrbbb → rrrbbb (このあとの衝突は色が異なるため消えない)

gbyw → ygbyw (色が合わないため、そのまま指定位置にボールを挿入)

ゲーム「Zuma」の作成

Input

Output

Examples

Explanation

Constraints

To check your solution you need to sign in

Sign in to continue