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.
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
- rrryyrrb → rrr
yyyrrb → rrrrrb → b
- rgbbrg → rg
bbrg → rgrg
- ggrrrbbb →
gggrrrbbb → rrrbbb (no collision between segments after this)
- gbyw →
ygbyw (the colors do not match ⇒ insert the ball at the index at which it was shot)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB