Діма та масив

Мама подарувала хлопчику Дімі масив довжиною $n$. Масив цей не простий, а особливий. Діма може вибрати два числа $i$ та $d(1\le i\le n,-1000\le d\le 1000)$, і елемент з індексом $i$ магічно стає рівним $d$. Діма бавиться зі своїм масивом, а мама час від часу задає йому питання — яка сума усіх чисел у масиві з індексами від $f$ до $t$? Діма легко справився з цими запитаннями, а чи зможете Ви?

Вхідні дані

У першому рядку знаходиться два цілих числа $n$ та $q(1\le n\le 5\cdot 10^5,1\le q\le 10^5)$ — кількість елементів у масиві і сумарна кількість операцій та запитів відповідно. У наступному рядку задано $n$ чисел $a_1,a_2,...,a_n(-1000\le a_i\le 1000)$ — початковий стан масиву. У наступних $q$ рядках задані операції та запити. Перший символ у рядку може бути $=$ або $?$. Якщо рядок починається з $=$, то це операція присвоювання. Далі йдуть $i$ та $d$, обмеження на які надано вище. Якщо рядок починається з $?$, то це запит. Далі йдуть числа $f$ та $t(1\le f,t\le n)$.

Вихідні дані

Для кожного запиту виведіть суму чисел у масиві з індексами від $f$ до $t$, по одному результату у рядку.

Приклади