题目描述

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