Time Limit: 1000MS

Memory Limit: 262144KB

64bit IO Format: %I64d & %I64u

 

Description

Sereja has got an array, consisting of n integers, a₁, a₂, ..., a_n. Sereja is an active boy, so he is now going to complete m operations. Each operation will have one of the three forms:

1. Make v_i-th array element equal to x_i. In other words, perform the assignment a_vi = x_i.
2. Increase each array element by y_i. In other words, perform n assignments a_i = a_i + y_i(1 ≤ i ≤ n).
3. Take a piece of paper and write out the q_i-th array element. That is, the element a_qi.

Help Sereja, complete all his operations.

Input

The first line contains integers n, m(1 ≤ n, m ≤ 10⁵). The second line contains n space-separated integers a₁, a₂, ..., a_n(1 ≤ a_i ≤ 10⁹) — the original array.

Next m lines describe operations, the i-th line describes the i-th operation. The first number in the i-th line is integer t_i(1 ≤ t_i ≤ 3) that represents the operation type. If t_i = 1, then it is followed by two integers v_i and x_i, (1 ≤ v_i ≤ n, 1 ≤ x_i ≤ 10⁹). If t_i = 2, then it is followed by integer y_i(1 ≤ y_i ≤ 10⁴). And if t_i = 3, then it is followed by integer q_i(1 ≤ q_i ≤ n).

Output

For each third type operation print value a_qi. Print the values in the order, in which the corresponding queries follow in the input.

Sample Input

Input

10 111 2 3 4 5 6 7 8 9 103 23 92 103 13 101 1 102 102 103 13 103 9

Output

291120304039

这道题目大家须要思考，不要一看到题目就用线段树，要想想有没有更好的方法，这里的题目给出的三种操作

能够知道没有一个是对区间进行操作的，唯一一个都是对整个数组操作。对全部的数的影响一样。

所以代码便能够变为例如以下：

/*Author: 2486Memory: 204 KB		Time: 93 MSLanguage: GNU G++11 4.9.2		Result: AcceptedVJ RunId: 4206974		Real RunId: 12270208Public:		No Yes*/#include 
            
             #include 
             
              #include 
              
               using namespace std;const int maxn=1e5+5;int n,m,p,c,v,a[maxn];int main() {    scanf("%d%d",&n,&m);    for(int i=1; i<=n; i++) {        scanf("%d",&a[i]);    }    int cnt=0;    while(m--) {        scanf("%d%d",&p,&c);        if(p==1) {            scanf("%d",&v);            a[c]=v-cnt;        } else if(p==2) {            cnt+=c;        } else {            printf("%d\n",a[c]+cnt);        }    }    return 0;}