← 返回题目列表

Codeforces · 1109/E

E. Sasha 和一个非常简单的测试

中文机器翻译题面 查看原题

叶戈尔喜欢数学,不久前他得到了数学界最高程度的认可——叶戈尔成为了一名红色数学家。对此,萨沙决定向叶戈尔表示祝贺,并送他一场数学考试作为礼物。该测试包含一个长度为 $$$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$$$