题目描述

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