P4588 [TJOI2018] Mathematical Calculation

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$.

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).

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

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