Заданий масив з \(N\) елементів. Це його версія номер 1.
Необхідно опрацьвоувати наступні запити:
1) В версії номер \(K\) змінити елемент в позиції \(pos\) на значення \(newval\)
2) Визначити в версії номер \(K\) суму елементів на відрізку \([L,R]\)
3) Створити нову версію масиву, копію версії номер \(K\)

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

В першому рядку два цілих числа \(N,Q\) - розмір масиву і кількість запитів. (\(1 \le N,Q \le 2*10^5\))
В наступному рядку \(N\) цілих чисел \(Ai\) - елементи масиву. (\(1 \le Ai \le 10^9\))
В наступних \(Q\) рядках містяться запити наступного виду:
\(1\) \(K\) \(pos\) \(newval\)
\(2\) \(K\) \(L\) \(R\)
\(3\) \(K\)

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

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

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

5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5

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

13
13
13
15