Xiao Dou has a number $x$, initially $1$. Xiao Dou performs $Q$ operations, which are of two types:

1. $m$: $x = x \times m$, output $x \pmod{mod}$;
2. $pos$: $x = x / (\text{the number multiplied in the } pos\text{-th operation})$. (It is guaranteed that the $pos$-th operation is of type 1, and each type 1 operation is divided at most once). Output $x \pmod{mod}$.

Input

There are $t$ test cases ($t \le 5$). For each test case, the first line contains two integers $Q$ and $mod$ ($Q \le 100000, mod \le 1000000000$). The next $Q$ lines each contain an operation type and the operation number or the number to be multiplied (it is guaranteed that all inputs are valid).

Output

For each operation, output the value of $x \pmod{mod}$ after the operation is performed.

Examples

Input 1

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

Output 1

2
1
2
20
10
1
6
42
504
84

Constraints

For 20% of the data, $1 \le Q \le 500$. For 100% of the data, $1 \le Q \le 100000$.