[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独家拥有在线测评使用权

Menuappsclose