题目描述

小 Z 有一个形如 $x ~ op_1 ~a_1 ~ op_2 ~a_2 ~ \cdots ~ op_n ~ a_n$ 的表达式，其中 $x$ 是变量， $a_i$ 是常量， $op_i$ 是 +,*,^ 表达式中的一个，其中 ^ 表示乘方，即 ^ 表示 。本题中定义 。表达式中的运算符没有优先级，全部从左往右计算。另外还有一个模数 $P$ 。

有 $m$ 个操作，操作有如下两种：

• 1 x0，表示求当 $x=x0$ 时表达式对 $P$ 取模的值；
• 2 p cx，表示将表达式中的 $op_p$ 修改为 $c$， $a_p$ 修改为 $x$。保证 $c$ 也是 +,*,^ 中的一个。

对于其中的所有询问操作输出答案。

输入格式

从 expr.in 文件读入数据。

第一行一个整数，表示测试点编号（样例的编号为 $0$ ）。

第二行三个正整数 $n,m,P$ 。

下面 $n$ 行，每行一个字符和一个整数，表示 $op_i$ 和 $a_i$ 。

再下面 $m$ 行，每行为一个操作，格式如题面。

输出格式

输出到 expr.out 文件。

对于每个询问操作输出答案。

样例

0
4 3 7
*4
^2
+4
*10
1 1
2 3 *3
1 2

4
2

0
5 4 29393
*4
+2
^3
+8
*6
1 2
1 3
2 3 *5
1 3

6048
16512
468

说明/提示