题目描述

Informatik verbindet dich und mich. 信息将你我连结。

B 君希望以维护一个长度为 $n$ 的数组，这个数组的下标为从 $1$ 到 $n$ 的正整数。

一共有 $m$ 个操作，可以分为两种：

• 0 l r 表示将第 $l$ 个到第 $r$ 个数（ $a_l,a_{l+1} ...a_r$）中的每一个数 $a_i$ 替换为 $c^{a_i}$，即 $c$ 的 $a_i$ 次方，其中 $c$ 是输入的一个常数，也就是执行赋值 $a_i = c^{a_i}$。
• 1 l r 求第 $l$ 个到第 $r$ 个数的和，也就是输出： $\sum_{i=l}^{r}a_i$

因为这个结果可能会很大，所以你只需要输出结果 $\bmod \space p$ 的值即可。

输入格式

第一行有四个整数 $n, m, p, c$，所有整数含义见问题描述。 接下来一行 $n$ 个整数，表示 $a$ 数组的初始值。 接下来 $m$ 行，每行三个整数，其中第一个整数表示了操作的类型。

• 如果是 $0$ 的话，表示这是一个修改操作，操作的参数为 $l, r$。
• 如果是 $1$ 的话，表示这是一个询问操作，操作的参数为 $l, r$。

输出格式

对于每个询问操作，输出一行，包括一个整数表示答案 $\bmod \space p$ 的值。

4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3

0
3

1 40 19910626 2
0
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1

1
2
4
16
65536
11418102
18325590
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558

提示

【数据范围】

对于 $0\%$ 的测试点，和样例一模一样；

对于另外 $10\%$ 的测试点，没有修改；

对于另外 $20\%$ 的测试点，每次修改操作只会修改一个位置（也就是 $l = r$ ），并且每个位置至多被修改一次；

• 对于另外 $10\%$ 的测试点， $p = 2$；

对于另外 $10\%$ 的测试点， $p = 3$；

对于另外 $10\%$ 的测试点， $p = 4$；

对于另外 $20\%$ 的测试点， $1\le n,m \le 100$；

对于 $100\%$ 的测试点， $1\le n,m \le 5\times 10^4$，$1 \le p \le 10^8$，$0< c < p$，$0 \le a_i < p$。