01204212/Zooma 2

Back to 01204212

This task is motivated by Zuma, a video game by PopCap Games.

In this version of the game, we add another game action, i.e., colored balls may disappear under the following rule:

If you shoot ball number i into the sequence, and ball i together with at least 2 other balls after it have the same color

(forming consecutive balls of length at least 3), all consecutive balls of the same color starting at ball i disappear.

This is slightly different from the actual Zuma game where balls of the same color in the sequence right before ball i can also form a sequence of at least 3 balls.

As in Zooma 1, there is a sequence of n colored balls that moves toward an exit. You can shoot another m colored balls into the sequence.

Find out the final sequence of the balls.

The balls in the original sequence are numbered from 1 to n. The balls that you shoot are numbered from n+1 to n+m.

Game play example

Input

• First line: n and m
• Next n lines: for 1 <= i <= n, line 1 + i specifies one integer c[i] the color of ball i.
• Next m lines: for 1 <= j <= m, line 1 + n + j specifies two integers d[j] and p[j]. d[j] is the color of ball n+j (this is your j-th ball), and p[j] is the number of the ball right after which you shoot this ball into the sequence. Note that p[j] < n + j.

Output

Your program should print n+m integers which are the ball numbers in the final sequence.

Next challenge

Check out Zooma 3.