Мама подарила мальчику Диме массив длины 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, по одному результату в строке.