Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Sereja and Array

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSereja has got an array, consisting of *n* integers, *a*_{1}, *a*_{2}, ..., *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:

- Make
*v*_{i}-th array element equal to*x*_{i}. In other words, perform the assignment*a*_{vi}=*x*_{i}. - Increase each array element by
*y*_{i}. In other words, perform*n*assignments*a*_{i}=*a*_{i}+*y*_{i}(1 ≤*i*≤*n*). - 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^{5}). The second line contains *n* space-separated integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{9}) — 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^{9}). If *t*_{i} = 2, then it is followed by integer *y*_{i} (1 ≤ *y*_{i} ≤ 10^{4}). 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.

Examples

Input

10 11

1 2 3 4 5 6 7 8 9 10

3 2

3 9

2 10

3 1

3 10

1 1 10

2 10

2 10

3 1

3 10

3 9

Output

2

9

11

20

30

40

39

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/28/2017 02:10:01 (c2).

Desktop version, switch to mobile version.
User lists

Name |
---|