[Shoi2017]相逢是问候
时间限制：40s 空间限制：512MB
题目描述
Informatikverbindetdichundmich.
信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以
分为两种：0 l r表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai次方，其中c是
输入的一个常数，也就是执行赋值ai=c^ai1 l r求第l个到第r个数的和，也就是输出：sigma(ai),l<=i<=rai因为
这个结果可能会很大，所以你只需要输出结果mod p的值即可。
输入格式
第一行有三个整数n,m,p,c，所有整数含义见问题描述。
接下来一行n个整数，表示a数组的初始值。
接下来m行，每行三个整数，其中第一个整数表示了操作的类型。
如果是0的话，表示这是一个修改操作，操作的参数为l,r。
如果是1的话，表示这是一个询问操作，操作的参数为l,r。
1 ≤ n ≤ 50000, 1 ≤ m ≤ 50000, 1 ≤ p ≤ 100000000, 0 < c <p, 0 ≤ ai < p
输出格式
对于每个询问操作，输出一行，包括一个整数表示答案mod p的值。
样例输入
4 4 7 2 1 2 3 4 0 1 4 1 2 4 0 1 4 1 1 3
样例输出
0 3
提示
鸣谢多名网友提供正确数据，已重测！
题目来源
黑吉辽沪冀晋六省联考&&鸣谢xlk授权本OJ独家拥有在线测评使用权