[AHOI2009]维护序列

内存限制：256 MB 时间限制：1000 ms

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。有长为 $N$ 的数列，不妨设为 $a_1,a_2,…,a_N$。

有如下三种操作形式：

(1) 把数列中的一段数全部乘一个值；

(2) 把数列中的一段数全部加一个值；

(3) 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 $P$ 的值。

第一行两个整数 $N$ 和 $P(1≤P≤1000000000)$。

第二行含有 $N$ 个非负整数，从左到右依次为 $a_1,a_2,…,a_N$， $(0≤ai≤1000000000,1≤i≤N)$。

第三行有一个整数 $M$，表示操作总数。

从第四行开始每行描述一个操作，输入的操作有以下三种形式：

操作 1：“1 t g c”（不含双引号）。表示把所有满足 $t≤i≤g$ 的 $a_i$ 改为 $a_i×c$ $(1≤t≤g≤N,0≤c≤1000000000)$。
操作 2：“2 t g c”（不含双引号）。表示把所有满足 $t≤i≤g$ 的 $a_i$ 改为 $a_i+c$ $(1≤t≤g≤N,0≤c≤1000000000)$。
操作 3：“3 t g”（不含双引号）。询问所有满足 $t≤i≤g$ 的 $a_i$ 的和模 $P$ 的值 $(1≤t≤g≤N)$。同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

对每个操作 $3$，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

样例输入 1

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

样例输出 1

2
35
8

$ \begin{matrix}数据编号 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\N= & 10 & 1000 & 1000 & 10000 & 60000 & 70000 & 80000 & 90000 & 100000 & 100000 \\M= & 10 & 1000 & 1000 & 10000 & 60000 & 70000 & 80000 & 90000 & 100000 & 100000\end{matrix}$