叶戈尔喜欢数学,不久前他得到了数学界最高程度的认可——叶戈尔成为了一名红色数学家。对此,萨沙决定向叶戈尔表示祝贺,并送他一场数学考试作为礼物。该测试包含一个长度为 $$$n$$$ 的整数数组 $$$a$$$ 和精确的 $$$q$$$ 查询。查询分为三种类型:
1.“1 l r x”— 将 $$$l$$$ 到 $$$r$$$ 范围内的每个数字乘以 $$$x$$$。
2. "2 p x" — 将 $$$p$$$ 位置的数字除以 $$$x$$$(保证整除)。
3. "3 l r" — 求 $$$l$$$ 到 $$$r$$$ 范围内所有元素的总和。
总和可能很大,因此 Sasha 要求 Egor 以某个整数 $$$mod$$$ 为模来计算总和。
但是由于Egor是一名红色数学家,他没有足够的时间来解决如此简单的任务,同时他也不想激怒Sasha,这就是为什么他要求你帮忙并为$$$3$$$-rd类型的所有查询找到答案。
输入
第一行包含两个整数 $$$n$$$ 和 $$$mod$$$ ($$$1 \le n \le 10^5$$$, $$$2 \le mod \le 10^9 + 9$$$) — 数组的大小和数字 $$$mod$$$。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) - 数组本身。
第三行包含一个整数 $$$q$$$($$$1 \le q \le 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行满足以下格式之一:
- 1 l r x ($$$1 \le l \le r \le n$$$, $$$1 \le x \le 10^5$$$) 表示您必须将 $$$l$$$ 到 $$$r$$$ 范围内的每个数字乘以 $$$x$$$。
- 2 p x ($$$1 \le p \le n$$$, $$$1 \le x \le 10^5$$$),表示您必须将 $$$p$$$ 位置上的数字除以 $$$x$$$(保证整除性)。
- 3 l r ($$$1 \le l \le r \le n$$$),意味着您必须找到从 $$$l$$$ 到 $$$r$$$ 范围内的元素之和。
保证至少有一个$$$3$$$-rd 类型的查询。
输出
对于 $$$3$$$-rd 类型的每个查询,在新行上以 $$$mod$$$ 为模打印答案。
示例
输入 #1
5 100 4 1 2 3 5 5 3 1 5 1 2 3 6 3 1 2 1 1 5 1 3 2 4
输出 #1
15 10 21
输入 #2
5 2 4 1 2 3 5 7 3 1 5 1 2 3 6 3 1 2 1 1 5 1 3 2 4 2 3 4 3 3 4
输出 #2
1 0 1 0
输入 #3
5 2100 1 2 3 4 5 10 1 1 3 12 1 1 5 10 2 5 50 3 2 4 1 4 4 28 2 4 7 3 1 2 3 3 4 2 3 3 3 1 5
输出 #3
640 360 520 641
注意
第一个例子:
初始数组为 $$$[4, 1, 2, 3, 5]$$$
- 在第一个查询中,您必须计算整个数组的总和,它等于 $$$(4 + 1 + 2 + 3 + 5) \bmod 100 = 15 \bmod 100 = 15$$$
- 在第二个查询中,您必须将 $$$2$$$ 到 $$$3$$$ 范围内的每个数字乘以 $$$6$$$。结果数组将是 $$$[4, 6, 12, 3, 5]$$$
- 在第三个查询中,您必须计算 $$$1$$$ 到 $$$2$$$ 范围内的总和,它等于 $$$(4 + 6) \bmod 100 = 10 \bmod 100 = 10$$$
- 在第四个查询中,您必须将 $$$1$$$ 到 $$$5$$$ 范围内的每个数字乘以 $$$1$$$。乘以 $$$1$$$ 不会影响数组。
- 在第五个查询中,您必须计算 $$$2$$$ 到 $$$4$$$ 范围内的总和,它等于 $$$(6 + 12 + 3) \bmod 100 = 21 \bmod 100 = 21$$$
第二个例子:
初始数组为 $$$[4, 1, 2, 3, 5]$$$
- 在第一个查询中,您必须计算整个数组的总和,它等于 $$$(4 + 1 + 2 + 3 + 5) \bmod 2 = 15 \bmod 2 = 1$$$
- 在第二个查询中,您必须将 $$$2$$$ 到 $$$3$$$ 范围内的每个数字乘以 $$$6$$$。结果数组将是 $$$[4, 6, 12, 3, 5]$$$
- 在第三个查询中,您必须计算 $$$1$$$ 到 $$$2$$$ 范围内的总和,它等于 $$$(4 + 6) \bmod 2 = 10 \bmod 2 = 0$$$
- 在第四个查询中,您必须将 $$$1$$$ 到 $$$5$$$ 范围内的每个数字乘以 $$$1$$$。乘以 $$$1$$$ 不会影响数组。
- 在第五个查询中,您必须计算 $$$2$$$ 到 $$$4$$$ 范围内的总和,它等于 $$$(6 + 12 + 3) \bmod 2 = 21 \bmod 2 = 1$$$
- 在第六个查询中,您必须将 $$$3$$$ 位置处的数字除以 $$$4$$$。 $$$\frac{12}{4}=3$$$,因此数组将为$$$[4, 6, 3, 3, 5]$$$。
- 在第七个查询中,您必须计算 $$$3$$$ 到 $$$4$$$ 范围内的总和,它等于 $$$(3 + 3) \bmod 2 = 6 \bmod 2 = 0$$$