题目描述

原题来自：AHOI 2009

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

有长为$\red{ n}$ 的数列，不妨设为 $\red{a_1,a_2,\cdots ,a_n}$​。有如下三种操作形式：

• 把数列中的一段数全部乘一个值；
• 把数列中的一段数全部加一个值；
• 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 $\red{P }$的值。

输入格式

第一行两个整数$\red{ n}$ 和 $\red{P}$；

第二行含有 $\red{n }$个非负整数，从左到右依次为 $\red{a_1,a_2,\cdots ,a_n}$；

第三行有一个整数 $\red{M}$，表示操作总数；

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

• 操作$\red{ 1}$：1 t g c，表示把所有满足 $\red{t\le i\le g}$ 的$\red{ a_i}$ 改为$\red{ a_i\times c}$；
• 操作$\red{ 2}$：2 t g c，表示把所有满足$\red{ t\le i\le g }$的$\red{ a_i​}$ 改为$\red{ a_i+c}$；
• 操作$\red{ 3}$：3 t g，询问所有满足$\red{ t\le i\le g}$ 的$\red{ a_i}$ 的和模$\red{ P }$的值。

同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输出格式

对每个操作 $\red{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

初始时数列为 $\red{\{1,2,3,4,5,6,7\}}$；

经过第 $\red{1 }$次操作后，数列为$\red{ \{1,10,15,20,25,6,7\}}$；

对第 $\red{2 }$次操作，和为$\red{ 10+15+20=45}$，模$\red{ 43}$ 的结果是$\red{ 2}$；

经过第 $\red{3 }$次操作后，数列为$\red{ \{1,10,24,29,34,15,16\}}$；

对第 $\red{4 }$次操作，和为$\red{ 1+10+24=35}$，模 $\red{43}$ 的结果是$\red{ 35}$；

对第$\red{ 5}$ 次操作，和为$\red{ 29+34+15+16=94}$，模 $\red{43}$ 的结果是 $\red{8}$。

提示

对于全部测试数据，$\red{1\le t\le g\le n,0\le c,a_i\le 10^9,1\le P\le 10^9+7}$。

测试数据规模如下表所示：

数据编号	$\red{ 1 }$	$\red{2,3 }$	$\red{4 }$	$\red{ 5 }$	$\red{6}$	$\red{7 }$	$\red{8 }$	$\red{9,10}$
$\red{n=}$	$\red{10}$	$\red{10^3}$	$\red{10^4 }$	$\red{ 6\times 10^4}$	$\red{ 7\times 10^4}$	$\red{ 8\times 10^4 }$	$\red{9\times 10^4 }$	$\red{10^5 }$
$\red{M=}$	$\red{ 10}$	$\red{ 10^3 }$		$\red{6\times 10^4 }$	$\red{ 7\times 10^4 }$	$\red{8\times 10^4 }$	$\red{9\times 10^4}$	$\red{ 10^5 }$