如题，已知一个数列，你需要进行下面三种操作：

• 将某区间每一个数乘上 $x$

• 将某区间每一个数加上 $x$

• 求出某区间每一个数的和

输入格式

第一行包含三个整数 $N$ 、 $M$ 、 $P$ ，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含$N$个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $M$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

操作$1$： 格式：1 x y k 含义：将区间$[x,y]$内每个数乘上$k$

操作$2$： 格式：2 x y k 含义：将区间$[x,y]$内每个数加上$k$

操作$3$： 格式：3 x y 含义：输出区间$[x,y]$内每个数的和对$P$取模所得的结果

输出格式

输出包含若干行整数，即为所有操作 $3$ 的结果。

样例

样例输入

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

样例输出

17
2

数据范围与提示

• 对于$30$%的数据：$N \leq 8，M \leq 10$
• 对于$70$%的数据：$N \leq 1000，M \leq 10000$
• 对于$100$%的数据：$N \leq 100000，M \leq 100000$
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$131072\mathrm{KB}$