В день детей ребенок пришел домой к Пиксу и все перевернул вверх дном. Пикс на него разозлился. В бардаке потерялось много всего, включая любимую последовательность Пикса.
К счастью, Пикс помнит, как можно восстановить последовательность. Сначала нужно завести целочисленный массив a[1], a[2], ..., a[n]. Затем нужно выполнить последовательно m операций. Операции могут быть такими:
- Операция вывода суммы (параметры l, r). Пикс должен записать значение
. - Операция взятия по модулю (параметры l, r, x). Пикс должен выполнить присвоения a[i] = a[i] mod x для каждого i (l ≤ i ≤ r).
- Операция изменения значения (параметры k, x). Пикс должен изменить значение a[k] на x (иными словами, выполнить присвоение a[k] = x).
Сможете ли вы помочь Пиксу выполнить заданную последовательность операций?
Выходные данные
Для каждой операции 1, выведите значение, которое должен записать Пикс. Обратите внимание, что ответ может не помещаться в 32-битное целое число.
Примечание
Рассмотрим первый тестовый пример:
- Сперва a = {1, 2, 3, 4, 5}.
- После операции 1, a = {1, 2, 3, 0, 1}.
- После операции 2, a = {1, 2, 5, 0, 1}.
- При операции 3, 2 + 5 + 0 + 1 = 8.
- После операции 4, a = {1, 2, 2, 0, 1}.
- При операции 5, 1 + 2 + 2 = 5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3
|
8
5
|
|
2
|
10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10
|
49
15
23
1
9
|