01204212/Zooma 3

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 before and after it have the same color

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

This is the expected behavior in the actual Zuma game.

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 you created 3 consecutive green balls, these balls would now disappear. You then get the following sequence:

        1     4     5
        B     Y     Y

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

        1     4     *7*     5
        B     Y     *Y*     Y

Again balls 4,7, and 5 would disappear. We would get the following output sequence:

        1
        B

If you shoot your third ball to the location after ball 4 (which has already disappeared), this ball disappears too.

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 3
1
2
2
3
3
2 3
3 4
3 4

Output

1

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:

4
8
15
12
19
9
10
16

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

3
81
56
86
6
62
7
8
9
10