题目描述

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为n的数列，不妨设为$a_1,a_2, \cdots,a_n$。有如下三种操作形式： 把数列中的一段数全部乘一个值；把数列中的一段数全部加一个值；询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

输入描述

第一行两个整数n和P； 第二行含有n个非负整数，从左到右依次为$a_1,a_2, \cdots,a_n$； 第三行有一个整数M，表示操作总数； 从第四行开始每行描述一个操作，输入的操作有以下三种形式：

操作1：1 t g c，表示把所有满足$t \le i \le g$的$a_i$改为$a_i \times c$；

操作2：2 t g c，表示把所有满足$t \le i \le g$的$a_i$改为$a_i+c$；

操作3：3 t g，询问所有满足$t \le i \le g$的$a_i$的和模P的值。

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

输出描述

对每个操作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

输出

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 \le t \le g \le n,0 \le c,a_i \le 10^9,1 \le P \le10^9$。。

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