只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
1798 - [Ahoi2009]Seq 维护序列seq
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a_1,a_2,…,a_N 。有如下三种操作形式：
- 把数列中的一段数全部乘一个值;
- 把数列中的一段数全部加一个值;
- 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模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，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
样例
输入
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
输出
2 35 8
提示
【样例说明】
初始时数列为(1,2,3,4,5,6,7)。
经过第1次操作后，数列为(1,10,15,20,25,6,7)。
对第2次操作，和为10+15+20=45，模43的结果是2。
经过第3次操作后，数列为(1,10,24,29,34,15,16)。
对第4次操作，和为1+10+24=35，模43的结果是35。
对第5次操作，和为29+34+15+16=94,模43的结果是8。
1\leq N\leq 10^5,1\leq M\leq 10^5