Description

Xiaodou now has a number $x$, initially $1$. There are $Q$ operations of two types:

1 m: set $x$ to $x \times m$, then output $x \bmod M$.

2 pos: set $x$ to $x$ divided by the number multiplied in the $pos$-th operation (it is guaranteed that the $pos$-th operation is of type 1, and each type 1 operation will be divided at most once), then output $x \bmod M$.

Input Format

There are $t$ test cases.

For each test case, the first line contains two integers $Q, M$.

The next $Q$ lines each contain an operation, formatted as either 1 m or 2 pos (all inputs are guaranteed to be valid).

Output Format

For each operation, output one line containing the value of $x \bmod M$ after executing the operation.

1
10 1000000000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7

2
1
2
20
10
1
6
42
504
84

Hint

For $20\%$ of the testdata, $1 \le Q \le 500$.

For $100\%$ of the testdata, $1 \le Q \le 10^5$, $t \le 5$, $1 \lt M \le 10^9$, $0 < m \leq 10^9$.

Translated by ChatGPT 5