Problem Q
Tea Party

The king of the rabbit country is hosting a tea party. In the party, there is a round table with $M$ chairs surrounding it. The chair is numbered from $0$ to $M-1$, and is set such that for each $0 \le i \le M-2$, the chair to the right of chair $i$ is chair $i+1$, and to the right of chair $M-1$ is chair $0$. Initially, all chairs are empty.

The sitting rule in the tea party is rather peculiar: Initially, a rabbit numbered $x$ will start from chair $(Ax + B) \mod M$. Then, the rabbit keep going to the right while the chair it is currently at is occupied. Finally, upon reaching an empty chair, the rabbit sits there. Note that, the rabbits in the rabbit country are numbered from $0$ to $10^9-1$.

The guards observed that there are $Q$ events happening throughout the tea party, each in the form of the following:

• The rabbit numbered $X$ enters the party. The guards know that such rabbit is currently not in the party, and they are sure that currently there is an empty chair.

• The rabbit numbered $X$ exits the party. The guards know that such rabbit is currently in the party. Furthermore, after this event, the chair the rabbit used is now empty.

While the guards cannot observe the party themselves, they are curious. Each time a rabbit enters the party, which chair the rabbit will sit on?

Input

The first line contains a single integer $SUB$ ($0 \le SUB \le 8$), denoting the subtask the input belongs to. Here, subtask $0$ refers to the sample test cases.

The second line contains four integers $A\; B\; M\; Q$ ($0 \le A < 10^9$, $0 \le B < 10^9$, $1 \le M \le 10^9$, $1 \le Q \le 200\; 000$), denoting the two parameters the rabbits use in their sitting rule, the number of the chairs, and the number of the events, respectively.

The next $Q$ lines will be in the form of the following:

• $1\; X$ ($0 \le X < 10^9$), meaning the rabbit numbered $X$ enters the party. It is guaranteed that currently such rabbit is not in the party and there is an empty chair.

• $2\; X$ ($0 \le X < 10^9$), meaning the rabbit numbered $X$ exits the party. It is guaranteed that currently such rabbit is in the party.

Output

For each “$1\; X$” event, output the chair the rabbit will sit on.

Subtasks

1. ($14$ Points): Only contains the following input:

       1
       2 3 10 7
       1 11
       1 2
       1 16
       1 21
       1 26
       2 21
       1 3
           

2. ($11$ Points): $A = 0$, and there is no “$2\; X$” event.

3. ($17$ Points): $M, Q \le 2\; 000$.

4. ($10$ Points): $Q \le 2\; 000$.

5. ($18$ Points): $M \le 200\; 000$, and there is no “$2\; X$” event.

6. ($10$ Points): $M \le 200\; 000$.

7. ($15$ Points): There is no “$2\; X$” event.

8. ($5$ Points): No additional constraints.

Explanation of Sample 1

There are $5$ chairs, and initially each of them is empty.

Then, the rabbit numbered $2$ enters the party. As $(1\cdot 2 + 2) \mod 5 = 4$ and chair $4$ is empty, it sits on chair $4$.

After that, the rabbit numbered $1$ enters the party. It sits on chair $3$.

Then, the rabbit numbered $6$ enters the party. As $(1\cdot 6 + 2) \mod 5 = 3$, it starts from chair $3$, keeps going to the right, until it sits on the first empty chair, which is chair $0$.

After that, the rabbit numbered $2$ exits the party. Thus, chair $4$ is now empty.

Then, the rabbit numbered $7$ enters the party. It sits on chair $4$.

Lastly, the rabbit numbered $2$ enters the party again. It starts from chair $4$, keeps going to the right, until it sits on the first empty chair, which is chair $1$.

Warning

The I/O files are large. Please use fast I/O methods.

0
1 2 5 6
1 2
1 1
1 6
2 2
1 7
1 2

4
3
0
4
1

0
0 7 10 5
1 2040
1 5
1 24
1 25
1 1

7
8
9
0
1

0
7777 77 100000000 7
1 1111111
1 2222222
1 3333333
2 2222222
1 4444444
1 5555555
1 6666666

41110324
82220571
23330818
64441065
5551312
46661559