A6336. 「SHOI2017」相逢是问候
编程题
省选/NOI-
知识点
题目描述
> Informatik verbindet dich und mich.
> 信息将你我连结。
B 君希望以维护一个长度为 $n$ 的数组，这个数组的下标为从 $1$ 到 $n$ 的正整数。
一共有 $m$ 个操作，可以分为两种：
* $0 \ l \ r$：表示将第 $l$ 个到第 $r$ 个数 $(a_l, a_{l+1}, \dots, a_r)$ 中的每一个数 $a_i$ 替换为 $c^{a_i}$，即 $c$ 的 $a_i$ 次方，其中 $c$ 是输入的一个常数，也就是执行赋值
$$a_i \leftarrow c^{a_i}$$
* $1 \ l \ r$：求第 $l$ 个到第 $r$ 个数的和，也就是输出：
$$\sum_{i = l}^r a_i$$
因为这个结果可能会很大，所以你只需要输出结果 $\mathrel{\mathrm{mod}} p$ 的值即可。
> 信息将你我连结。
B 君希望以维护一个长度为 $n$ 的数组，这个数组的下标为从 $1$ 到 $n$ 的正整数。
一共有 $m$ 个操作，可以分为两种：
* $0 \ l \ r$：表示将第 $l$ 个到第 $r$ 个数 $(a_l, a_{l+1}, \dots, a_r)$ 中的每一个数 $a_i$ 替换为 $c^{a_i}$，即 $c$ 的 $a_i$ 次方，其中 $c$ 是输入的一个常数，也就是执行赋值
$$a_i \leftarrow c^{a_i}$$
* $1 \ l \ r$：求第 $l$ 个到第 $r$ 个数的和，也就是输出：
$$\sum_{i = l}^r a_i$$
因为这个结果可能会很大，所以你只需要输出结果 $\mathrel{\mathrm{mod}} p$ 的值即可。
输入格式
第一行有四个整数 $n, m, p, c$，所有整数含义见问题描述。
接下来一行 $n$ 个整数，表示 $a$ 数组的初始值。
接下来 $m$ 行，每行三个整数，其中第一个整数表示了操作的类型。
* 如果是 $0$ 的话，表示这是一个修改操作，操作的参数为 $l, r$。
* 如果是 $1$ 的话，表示这是一个询问操作，操作的参数为 $l, r$。
接下来一行 $n$ 个整数，表示 $a$ 数组的初始值。
接下来 $m$ 行，每行三个整数，其中第一个整数表示了操作的类型。
* 如果是 $0$ 的话，表示这是一个修改操作，操作的参数为 $l, r$。
* 如果是 $1$ 的话，表示这是一个询问操作，操作的参数为 $l, r$。
输出格式
对于每个询问操作，输出一行，包括一个整数表示答案 $\mathrel{\mathrm{mod}} p$ 的值。
输入输出样例
输入 #1
4 4 7 2 1 2 3 4 0 1 4 1 2 4 0 1 4 1 1 3
输出 #1
0 3
输入 #2
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
输出 #2
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\%$ 的测试点，$n \le 100$，$m \le 100$；
对于 $100\%$ 的测试点，$1 \le n \le 50000$，$1 \le m \le 50000$，$1 \le p \le 100000000$，$1 \le c < p$，$0 \le a_i < p$。
对于另外 $10\%$ 的测试点，没有修改；
对于另外 $20\%$ 的测试点，每次修改操作只会修改一个位置（也就是 $l = r$），并且每个位置至多被修改一次；
对于另外 $10\%$ 的测试点，$p = 2$；
对于另外 $10\%$ 的测试点，$p = 3$；
对于另外 $10\%$ 的测试点，$p = 4$；
对于另外 $20\%$ 的测试点，$n \le 100$，$m \le 100$；
对于 $100\%$ 的测试点，$1 \le n \le 50000$，$1 \le m \le 50000$，$1 \le p \le 100000000$，$1 \le c < p$，$0 \le a_i < p$。