Мама подарувала хлопчику Дімі масив довжиною n. Масив цей не простий, а особливий. Діма може вибрати два числа i та d(1≤i≤n,−1000≤d≤1000), і елемент з індексом i магічно стає рівним d. Діма бавиться зі своїм масивом, а мама час від часу задає йому питання — яка сума усіх чисел у масиві з індексами від f до t? Діма легко справився з цими запитаннями, а чи зможете Ви?
У першому рядку знаходиться два цілих числа n та q(1≤n≤5⋅105,1≤q≤105) — кількість елементів у масиві і сумарна кількість операцій та запитів відповідно. У наступному рядку задано n чисел a1,a2,...,an(−1000≤ai≤1000) — початковий стан масиву. У наступних q рядках задані операції та запити. Перший символ у рядку може бути = або ?. Якщо рядок починається з =, то це операція присвоювання. Далі йдуть i та d, обмеження на які надано вище. Якщо рядок починається з ?, то це запит. Далі йдуть числа f та t(1≤f,t≤n).
Для кожного запиту виведіть суму чисел у масиві з індексами від f до t, по одному результату у рядку.