题目背景

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

题目描述

有一个长为 \(n\) 的数列 \(\{a_n\}\)，有如下三种操作形式：

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\) 的值。

格式

输入格式

第一行两个整数 \(n\) 和 \(p\)。

第二行含有 \(n\) 个非负整数，表示数列 \(\{a_i\}\) 。

第三行有一个整数 \(m\)，表示操作总数。

从第四行开始每行描述一个操作，同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输出格式

对每个操作 3，按照它在输入中出现的顺序，依次输出 一行一个整数 表示询问结果。

样例1

样例输入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\}\)。
• 经过第 \(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	2	3	4	5	6	7	8	9,10
\(n=\)	\(10\)	\(1000\)	\(1000\)	\(10000\)	\(60000\)	\(70000\)	\(80000\)	\(90000\)	\(100000\)
\(m=\)	\(10\)	\(1000\)	\(1000\)	\(10000\)	\(60000\)	\(70000\)	\(80000\)	\(90000\)	\(100000\)

对于全部的测试点，保证 \(0 \leq p, a_i, c \leq 10^9\)，\(1 \leq t \leq g \leq n\)。