F. Mod
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

To train your ability to calculate huge numerical values, $$$Irelia$$$ requires you to perform $$$n$$$ operations. Let $$$a_i$$$ denote the result produced by the $$$i$$$-th operation.

Each operation is one of the following four forms:

  • = v: assign $$$a_i = v$$$.
  • + j k: assign $$$a_i = a_j + a_k$$$.
  • * j k: assign $$$a_i = a_j \times a_k$$$.
  • ^ j k: assign $$$a_i = a_j^{a_k}$$$.

After each operation, output the value of $$$a_i$$$ modulo $$$m$$$.

Please note that the modulo operation is only applied to the answer, and the actual value of $$$a_i$$$ may be huge.

Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 201307$$$, $$$2 \leq m \leq 10^9$$$), representing the number of operations and the modulus.

In the next $$$n$$$ lines, each contains an operation. For the $$$i$$$-th line, it starts with a character $$$op$$$ ($$$op \in \{\text{=,+,*,^}\}$$$). If $$$op$$$ is "=", it is followed by an integer $$$v$$$ ($$$1 \leq v \leq 10^9$$$). Otherwise, $$$op$$$ is followed by two integers $$$j$$$ and $$$k$$$ ($$$1 \leq j, k \lt i$$$).

Output

After each operation, output the value of $$$a_i$$$ modulo $$$m$$$.

Examples
Input
4 201307
= 1
+ 1 1
* 2 2
^ 3 3
Output
1
2
4
256
Input
6 8
= 5
+ 1 1
^ 2 1
^ 2 2
= 8
= 9
Output
5
2
0
0
0
1