Creating the Zuma game

You’ve decided to create the game Zuma. You’re now working on the part that removes segments of balls having the same color when the segments hit each other. So, having a list of balls with different colors, the player shoots with a ball of some color to a specific position in that line. If there are more than 2 balls with the same color at that segment (including the ball shot by the player), that segment of balls disappears, and the balls surrounding it fill the gap.
notion image
If 3 or more balls colliding have the same color, that segment of balls with the same color disappears as well. This process continues until the colliding segments have different colors or there are no balls left.

Input

The first line of the input contains a single string b (1 ≤ |b| ≤ ) representing the balls in the line. The colors of the balls are represented as lowercase Latin letters (y for yellow, b for blue, r for red, etc).
The next line contains the index at which the user shoots a ball i (1 ≤ i ≤ |b|) and the color of the ball c (lowercase Latin letter).

Output

The programs should print the resulting sequence of balls.

Examples

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

Explanation

  1. rrryyrrb → rrryyyrrb → rrrrrb → b
  1. rgbbrg → rgbbrg → rgrg
  1. ggrrrbbb → gggrrrbbb → rrrbbb (no collision between segments after this)
  1. gbyw → ygbyw (the colors do not match ⇒ insert the ball at the index at which it was shot)
 

Constraints

Time limit: 2.4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in