Егор очень любит математику, и недавно он получил высшую степень признания в математических кругах — Егор стал красным математиком. По такому поводу Саша решил поздравить Егора и подарить ему математический тест. В тесте содержался массив \(a\) длины \(n\) из целых чисел и ровно \(q\) запросов. Запросы бывают трёх типов:
- «1 l r x» — увеличить все числа на отрезке от \(l\) до \(r\) в \(x\) раз.
- «2 p x» — уменьшить число в позиции \(p\) в \(x\) раз (делимость гарантирована).
- «3 l r» — найти сумму на отрезке от \(l\) до \(r\).
Так как сумма может быть очень большой, то Саша попросил Егора вычислить лишь её остаток от деления на число \(mod\).
Так как Егор теперь красный математик, ему больше некогда решать столь простые задачи, поэтому, чтобы не обидеть Сашу, он попросил вас помочь ему и найти ответы на все запросы \(3\)-го типа.
Выходные данные
Для каждого запроса \(3\)-го типа в отдельной строке выведите ответ на запрос по модулю \(mod\).
Примечание
Первый пример:
Изначальный массив — \([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\)
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|
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
|
640
360
520
641
|