题目描述

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

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

1. 把数列中的一段数全部乘一个值；
2. 把数列中的一段数全部加一个值；
3. 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 $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

输出样例 1

2
35
8

样例解释

初始数列：$[1, 2, 3, 4, 5, 6, 7]$，$P = 43$。

1. 1 2 5 5：将 $a_2 \sim a_5$ 都乘以 $5$，数列变为 $[1, 10, 15, 20, 25, 6, 7]$。
2. 3 2 4：询问 $a_2 + a_3 + a_4 = 10 + 15 + 20 = 45$，$45 \bmod 43 = 2$。
3. 2 3 7 9：将 $a_3 \sim a_7$ 都加上 $9$，数列变为 $[1, 10, 24, 29, 34, 15, 16]$。
4. 3 1 3：询问 $a_1 + a_2 + a_3 = 1 + 10 + 24 = 35$，$35 \bmod 43 = 35$。
5. 3 4 7：询问 $a_4 + a_5 + a_6 + a_7 = 29 + 34 + 15 + 16 = 94$，$94 \bmod 43 = 8$。

数据范围

• $1 \le t \le g \le n$
• $0 \le c, a_i \le 10^9$
• $1 \le P \le 10^9$

详细数据规模如下：

时间限制：1000 ms
内存限制：524288 KB

提示

这是一个典型的区间修改、区间查询问题，需要使用支持区间加、区间乘、区间求和的线段树（懒标记需要同时维护加法和乘法标记，注意标记下传的顺序）。

注意所有运算在模 $P$ 意义下进行，但 $P$ 不一定是质数，不能直接使用除法逆元。
数据较大，注意使用 long long 类型并适时取模。