#1573. BIT I: Single Modify, Interval Query

BIT I: Single Modify, Interval Query

Description

Given a sequence a1,a2,,ana_1, a_2, \dots, a_n, There're qq operations you need do execute, divided into two types:

  • 1 i x: Given i,xi,x, add xx to aia_i;
  • 2 l r: Given l,rl,r, print out i=lrai\sum_{i=l}^r a_i (i.e. al+al+1++ara_l+a_{l+1}+\dots+a_r).

Input

The first line contains 2 integers n,qn, q — the sequence length and the number of queries. 1n,q1061\le n,q\le 10^6.

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n — the initial sequence. ai106|a_i|\le 10^6.

Each of the next qq lines contains an operation, 1 i x or 2 l r.
1lrn,1\le l\le r\le n, x106|x|\le 10^6

Output

Each line prints the sum i=lrai\sum_{i=l}^r a_i for an operation 2.

Sample

3 2
1 2 3
1 2 0
2 1 3
6

Limits And Hints

All cases satisfiy 1n,q106,1\le n,q\le 10^6, ai106|a_i|\le 10^6, 1lrn,1\le l\le r\le n, x106|x|\le 10^6.