Заданий масив з \(N\) цілих чисел.

Необхідно обробляти наступні запити:
1 \(L\) \(R\) - знайти суму чисел на відрізку \(L\)..\(R\)
2 \(L\) \(R\) \(X\) - замінити на відрізку всі числа \(A[i]\) на \(A[i] mod X\) - замінити кожне число остачею від ділення на \(X\)
3 \(pos\) \(X\) - змінити елемент в позиції \(pos\) на \(X\)

Формат вхідних даних

В першому рядку \(N\) , \(M\) - кількість елементів масиву та кількість запитів (\(1 \le N,M \le 10^5\))
В наступному рядку \(N\) цілих чисел - елементи масиву (\(1 \le Ai \le 10^9\))
В кожному з наступних \(M\) рядків міститься опис відповідного запиту
кожен запит починається числом \(type\) - яке позначає тип запиту (1,2,3)
Якщо \(type=1\) то далі йдуть два числа \(L\) \(R\) (\(1 \le L \le R \le N\))
Якщо \(type=2\) то далі три числа \(L\) \(R\) \(X\) (\(1 \le L \le R \le N\)) , (\(1 \le X \le 10^9\))
Якщо \(type=3\) то далі два числа \(pos\) \(X\) (\(1 \le pos \le N\)) , (\(1 \le X \le 10^9\))

Формат вихідних даних

Для кожного запиту типу 1 иведіть відповідь в окремому рядку

Приклад вхідних даних-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

Приклад вихідних даних-1

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

Приклад вихідних даних-2

49
15
23
1
9