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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

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

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

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

Output

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

Constraints

\(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\).

Samples

Input (stdin) сopy	Output (stdout) сopy
8 3 1 4 2 1 7 3 5 2 1 2 6 2 4 4 1 2 6	17 21