时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以分为两种：
0 l r表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai次方，其中c是输入的一个常数，也就是执行赋值ai=c^ai
1 l r求第l个到第r个数的和，也就是输出：sigma(ai),l ≤ i ≤ r，ai
因为这个结果可能会很大，所以你只需要输出结果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的值。
备注:
对于0%的测试点，和样例一模一样；
对于另外10%的测试点，没有修改；
对于另外20%的测试点，每次修改操作只会修改一个位置（也就是
），并且每个位置至多被修改一次；
• 对于另外10%的测试点，
；
对于另外 10%的测试点，
；
对于另外10%的测试点，
；
对于另外20%的测试点，
；
对于100%的测试点，
。