Description

“神州“载人飞船的发射成功让小可可非常激动，他立志长大后要成为一名宇航员假期一始，他就报名参加了“小小宇航员夏令营”，在这里小可可不仅学到了丰富的宇航知识，还参与解决了一些模拟飞行中发现的问题，今天指导老师交给他一个任务，在这次模拟飞行的路线上有N个行星，暂且称它们为一个行星序列，并将他们从1至n标号，在宇宙未知力量的作用下这N个行星的质量是不断变化的，所以他们对飞船产生的引力也会不断变化，小可可的任务就是在飞行途中计算这个行星序列中某段行星的质量和，以便能及时修正飞船的飞行线路，最终到达目的地，行星序列质量变化有两种形式：

1.行星序列中某一段行星的质量全部乘以一个值

2.行星序列中某一段行星的质量全部加上一个值

由于行星的质量和很大，所以求出某段行星的质量和后只要输出这个值模P的结果即可，小可可被这个任务难住了，聪明的你能够帮他完成这个任务吗？

Input Format

第一行两个整数N和P（1<=p<=1000000000）；

第二行含有N个非负整数，从左到右依次为a1，a2，………，an（0<=ai<=100000000，1<=i<=n），其中ai表示第i个行星的质量：

第三行有一个整数m，表示模拟行星质量变化以及求质量和等操作的总次数。

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

操作1：1 t g c 表示把所有满足t<=i<=g的行星质量ai改为ai＊c

操作2：2 t g c 表示把所有满足t<=i<=g的行星质量ai改为ai＋c

操作3：3 t g 表示输出所有满足t<=i<=g的ai的和模p的值

其中：1<=t<=g<=N，0<=c<=10000000

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

Output Format

对每个操作3，按照它在输入中出现的顺序，依次一行输出一个整数表示所求行星质量和

Sample

【输入样例】

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。

Hint

100%的数据中，M，N<=100000

40%的数据中，M，N<=10000