L. Not A DS Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$M$$$ and you have an empty array $$$a$$$. You have to process $$$q$$$ queries on array $$$a$$$, there are two types of queries :

  • $$$1$$$ $$$x$$$ $$$k$$$ $$$(1 \le x \le 10^9, \ 2 \le k \le M)$$$ : insert $$$x$$$ at positions $$$1, k + 1, 2 * k + 1, \dots ,\left\lfloor \frac{length(a)}{k - 1} \right\rfloor * k + 1$$$, where $$$length(a)$$$ is the length of array $$$a$$$ before the inserting the number. for example if the array was $$$[1,1,1,1,1,1,1]$$$ and the query was $$$1$$$ $$$2$$$ $$$3$$$, the array will become : $$$[2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1]$$$.
  • $$$2$$$ : print the first element of the array and then delete it.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t (1 \le t \le 5 \cdot 10 ^ 4)$$$. The description of the test cases follows.

The first line of each test case contains two integers $$$q$$$ and $$$M$$$ $$$(2 \le q, \ 2 \le M, \ \mathbf{q * M \le 3 \cdot 10 ^ 5})$$$.

Each of the next $$$q$$$ lines contains the description of a query in one of the following formats:

  • $$$1 \ x \ k \ (1 \le x \le 10^9, \ 2 \le k \le M)$$$ — an insertion query.
  • $$$2$$$ — a deletion and print query. It is guaranteed that the array is not empty when a query of type $$$2$$$ is called.

It is guaranteed that the sum of $$$\mathbf{q * M}$$$ across all test cases does not exceed $$$\mathbf{3 \cdot 10 ^ 5}$$$.

Output

Output the answer for each query of the second type.

Example
Input
1
8 3
1 1 2
1 2 2
1 3 2
2
2
1 2 3
2
2
Output
3
2
2
3
Note

here is how the array $$$a$$$ changes during the queries :

  • initially : $$$a=[ \ ]$$$
  • after the first query : $$$a=[1]$$$
  • after the second query : $$$a=[2,1,2]$$$
  • after the third query : $$$a=[3,2,3,1,3,2,3]$$$
  • after the fourth query : $$$a=[2,3,1,3,2,3]$$$
  • after the fifth query : $$$a=[3,1,3,2,3]$$$
  • after the sixth query : $$$a=[2,3,1,2,3,2,2,3]$$$
  • after the seventh query : $$$a=[3,1,2,3,2,2,3]$$$
  • after the eighth query : $$$a=[1,2,3,2,2,3]$$$