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. As balls can disappear, if you shoot the ball that lands right after a particular ball that has already disappeared, the new ball also disappears too (see example)

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

Consider the case where n=5 and m=5. The original sequence has balls with these colors:

        1     2     3     4     5
        B     G     G     Y     Y

You have 5 balls numbered as this:

        6     7     8     9     10
        G     Y     Y     G     G

If you shoot your first ball to the location after ball 3, the sequence becomes

        1     2     3     *6*     4     5
        B     G     G     *G*     Y     Y

Note that although you created 3 consecutive green balls, the balls do not disappear because ball 6 is not the first ball in the sequence.

If you shoot your second ball to the location after ball 4, the sequence becomes

        1     2     3     6     4     *7*     5
        B     G     G     G     Y     *Y*     Y

Again no balls disappear because the sequence of yellow balls starting at ball 7 is of length 2.

If you shoot your third ball to the location after ball 4 again, the sequence becomes

        1     2     3     6     4     *8*     7     5
        B     G     G     G     Y     *Y*     Y     Y

Now starting at ball 8, you form a sequence of at least 3 balls, all these balls disappear. And you get the following sequence:

        1     2     3     6     4
        B     G     G     G     Y

If you shoot your forth ball to the location after ball 7 which has already disappeared, this ball disappears too. The sequence remains the same.

        1     2     3     6     4
        B     G     G     G     Y

If you shoot the last ball to the location after ball 1, the sequence becomes

        1     *10*    2     3     6     4
        B     *G*     G     G     G     Y

Ball 10 forms a consecutive sequence of 4 green balls. So they all disappear and the sequence changes to

        1     4
        B     Y

and this is the final sequence.

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. If ball p[j] has already disappeared, ball n+j will just disappears without hitting the sequence.

Limits in grader: In the grader n <= 100,000 and m <= 100,000. The time limit is 3 seconds.

Output

Your program should print a sequence of integers which are the ball numbers in the final sequence, one per line.

Example

Input (same as in the previous example, but color B = 1, G = 2, Y = 3;

5 5
1
2
2
3
3
2 3
3 4
3 4
2 7
2 1

Output

1
4

Test data

Use the same test data as in Zooma 1 task. Download at: http://theory.cpe.ku.ac.th/~jittat/courses/01204212/tasks/zooma1/

Expected output for n10-3.in:

1
2
13
4
5
8
15
12
19
9
10
16

Expected output for n50-3.in (first 10 lines):

1
61
2
97
52
3
81
4
56
86

Next challenge

Check out Zooma 3.