[六省联考2017]相逢是问候

题目描述

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$ 因为这个结果可能会很大,所以你只需要输出结果 mod p 的值即可。

输入输出格式

输入格式


第一行有四个整数 $n, m, p, c$,所有整数含义见问题描述。 接下来一行 $n$ 个整数,表示 $a$ 数组的初始值。 接下来 $m$ 行,每行三个整数,其中第一个整数表示了操作的类型。 - 如果是 $0$ 的话,表示这是一个修改操作,操作的参数为 $l, r$。 - 如果是 $1$ 的话,表示这是一个询问操作,操作的参数为 $l, r$。

输出格式


对于每个询问操作,输出一行,包括一个整数表示答案 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

说明

• 对于 0% 的测试点,和样例一模一样; • 对于另外 10% 的测试点,没有修改; • 对于另外 20% 的测试点,每次修改操作只会修改一个位置(也就是 l = r),并且每个位置至多被修改一次; • 对于另外 10% 的测试点, p = 2; • 对于另外 10% 的测试点, p = 3; • 对于另外 10% 的测试点, p = 4; • 对于另外 20% 的测试点, n ≤ 100; m ≤ 100; • 对于 100% 的测试点, 1 ≤ n ≤ 50000; 1 ≤ m ≤ 50000; 1 ≤ p ≤ 100000000; 0 < c