| Codeforces Round 250 (Div. 1) |
|---|
| Закончено |
В день детей ребенок пришел домой к Пиксу и все перевернул вверх дном. Пикс на него разозлился. В бардаке потерялось много всего, включая любимую последовательность Пикса.
К счастью, Пикс помнит, как можно восстановить последовательность. Сначала нужно завести целочисленный массив 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).
Сможете ли вы помочь Пиксу выполнить заданную последовательность операций?
В первой строке записано два целых числа: n, m (1 ≤ n, m ≤ 105). Во второй строке записано n целых чисел через пробел: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — начальное значение элементов массива.
Каждая из следующих m строк начинается с целого числа type 
.
- Если type = 1, то далее в строке идут два целых числа: l, r (1 ≤ l ≤ r ≤ n) — описание операции 1.
- Если type = 2, то далее в строке идут еще три целых числа: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109) — описание операции 2.
- Если type = 3, то далее в строке идут два целых числа: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109) — описание операции 3.
Для каждой операции 1, выведите значение, которое должен записать Пикс. Обратите внимание, что ответ может не помещаться в 32-битное целое число.
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
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
Рассмотрим первый тестовый пример:
- Сперва 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.
