Given an array ~ A ~ of ~ N ~ positive integers ~ A_1, A_2, \ldots, A_N ~ and ~ Q ~ operations, each operation can be one of the following types:

• Type ~1~: ~p_i~, ~x_i ~: Increase the element at position ~ p_i ~ by ~ x_i ~ units.
• Type ~2~: ~u_i~, ~v_i ~: Calculate the sum of elements from position ~ u_i ~ to ~ v_i ~ inclusive.

Input

• First line: Two positive integers ~N~ and ~Q~.
• Second line: ~N~ positive integers ~A_1, A_2, \ldots, A_N~ representing the array.
• Next ~Q~ lines: Each line contains an operation which can either be:
  • Type ~1~: ~1~ ~p_i~ ~x_i~
  • Type ~2~: ~2~ ~u_i~ ~v_i~

Output

• For each Type ~2~ operation, output the sum of elements from position ~u_i~ to ~ v_i ~ on a new line.

Constraints

• ~1 \leq N \leq 10^5~
• ~1 \leq Q \leq 10^5~
• ~A_i \leq 10^9~
• ~1 \leq p_i, u_i, v_i \leq N~
• ~1 \leq x_i \leq 10^9~

Sample Input

6 5
9 2 4 7 4 8
1 5 6
2 1 5
1 3 8
1 2 3
2 2 4 

Sample Output

32
24