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

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