E. Саша и очень лёгкий тест
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Егор очень любит математику, и недавно он получил высшую степень признания в математических кругах — Егор стал красным математиком. По такому поводу Саша решил поздравить Егора и подарить ему математический тест. В тесте содержался массив $$$a$$$ длины $$$n$$$ из целых чисел и ровно $$$q$$$ запросов. Запросы бывают трёх типов:

  1. «1 l r x» — увеличить все числа на отрезке от $$$l$$$ до $$$r$$$ в $$$x$$$ раз.
  2. «2 p x» — уменьшить число в позиции $$$p$$$ в $$$x$$$ раз (делимость гарантирована).
  3. «3 l r» — найти сумму на отрезке от $$$l$$$ до $$$r$$$.

Так как сумма может быть очень большой, то Саша попросил Егора вычислить лишь её остаток от деления на число $$$mod$$$.

Так как Егор теперь красный математик, ему больше некогда решать столь простые задачи, поэтому, чтобы не обидеть Сашу, он попросил вас помочь ему и найти ответы на все запросы $$$3$$$-го типа.

Входные данные

Первая строка содержит два целых числа $$$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$$$-го типа.

Выходные данные

Для каждого запроса $$$3$$$-го типа в отдельной строке выведите ответ на запрос по модулю $$$mod$$$.

Примеры
Входные данные
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
Выходные данные
15
10
21
Входные данные
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
Выходные данные
1
0
1
0
Входные данные
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
Выходные данные
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$$$