Найпростіші запити

Обмеження: 2 сек., 256 МіБ

Задано масив \(a\) із \(n\) цілих чисел. Потрібно відповісти на \(m\) запитів, кожен з яких одного із двох типів:

1. знайти суму елементів масиву на проміжку від \(l\) до \(r\) включно,

2. додати число \(d\) до \(i\)-го елементу масиву.

Вхідні дані

У першому рядку задано два цілих числа \(n\) і \(m\) — розмір масиву та кількість запитів відповідно.

У другому рядку задано \(n\) цілих чисел \(a_i\) — елементи масиву.

У наступних \(m\) рядках задано запити, по одному у рядку, у такому форматі:

• 1 l r — запит першого типу,

• 2 i d — запит другого типу.

Вихідні дані

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

Обмеження

\(1 \le n, m \le 10^5\).

\(-10^3 \le a_i, d \le 10^3\).

\(1 \le l, r, i \le n\).

\(l \le r\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
8 3 1 4 2 1 7 3 5 2 1 2 6 2 4 4 1 2 6	17 21