Description

There are $m$ groups and $n$ elements. Each element belongs to exactly one group.

Support the following operations:

push x: Enqueue element x. If there is already an element from x’s group ahead in the queue, x will be placed immediately after the last element of its own group currently in the queue; otherwise, x will be placed at the end of the whole queue.

pop: Dequeue. Remove the front element of the queue and output it. This behaves like a normal queue, i.e., elements in front leave first.

Input Format

The first line contains two positive integers $n$, $m$, representing the number of elements and the number of groups. Elements and groups are numbered starting from $0$.

The next line contains $n$ non-negative integers $A_i$, where $A_i$ is the group that element $i$ belongs to.

The next line contains a positive integer $T$, the number of operations.

The next $T$ lines each contain one operation.

Output Format

For each dequeue operation, output the dequeued element on a separate line.

4 2
0 0 1 1
6
push 2
push 0
push 3
pop
pop
pop

2
3
0

Hint

For $30\%$ of the testdata, $1 \le n \le 100$, $1 \le m \le 10$, $T \le 50$.

For $100\%$ of the testdata, $1 \le n \le 100000$, $1 \le m \le 300$, $T \le 100000$. The input guarantees that all operations are valid.

Translated by ChatGPT 5