为了训练你计算极大数值的能力，Irelia 要求你执行 $n$ 次操作。 设 $a_i$ 表示第 $i$ 次操作产生的结果。

每次操作为以下四种形式之一：

• = v：赋值 $a_i = v$。
• + j k：赋值 $a_i = a_j + a_k$。
• * j k：赋值 $a_i = a_j \times a_k$。
• ^ j k：赋值 $a_i = a_j^{a_k}$。

在每次操作后，输出 $a_i$ 模 $m$ 的值。

请注意，模运算仅应用于输出的答案，而 $a_i$ 的实际值可能会非常巨大。

输入格式

每个测试文件中只有一组测试数据。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 201307$，$2 \le m \le 10^9$），分别表示操作次数和模数。

接下来的 $n$ 行，每行包含一个操作。对于第 $i$ 行，它以一个字符 $op$（$op \in \{=, +, *, \^\}$）开头。如果 $op$ 为 "="，则后面跟着一个整数 $v$（$1 \le v \le 10^9$）。否则，$op$ 后面跟着两个整数 $j$ 和 $k$（$1 \le j, k < i$）。

输出格式

在每次操作后，输出 $a_i$ 模 $m$ 的值。

样例

输入样例 1

4 201307
= 1
+ 1 1
* 2 2
^ 3 3

输出样例 1

1
2
4
256

输入样例 2

6 8
= 5
+ 1 1
^ 2 1
^ 2 2
= 8
= 9

输出样例 2

5
2
0
0
0
1