Simplest Queries

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Given an array \(a\) of \(n\) integers. You need to answer \(m\) queries, each of which is of one of two types:

1. find the sum of array elements in the range from \(l\) to \(r\) inclusive,

2. add the number \(d\) to the \(i\)-th element of the array.

Input

The first line contains two integers \(n\) and \(m\) — the size of the array and the number of queries, respectively.

The second line contains \(n\) integers \(a_i\) — the elements of the array.

The next \(m\) lines contain queries, one per line, in the following format:

• 1 l r — query of the first type,

• 2 i d — query of the second type.

Output

For each query of the first type, print, on a separate line, the sum on the corresponding segment.

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