Sereja has got an array, consisting of n integers a1,a2,...,an. Sereja is an active boy, so he is now going to complete m operations. Each operation will have one of the three forms:
Make vi-th array element equal to xi. In other words, perform the assignment avi=xi.
Increase each array element by yi. In other words, perform n assignments ai=ai+yi (1≤i≤n).
Take a piece of paper and write out the qi-th array element. That is, the element aqi.
Help Sereja, complete all his operations.
The first line contains integers n,m (1≤n,m≤105). The second line contains n integers a1,a2,...,an (1≤ai≤109) — 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 ti (1≤ti≤3), that represents the operation type.
If ti=1, then it is followed by two integers vi and xi (1≤vi≤n,1≤xi≤109).
If ti=2, then it is followed by integer yi (1≤yi≤104).
If ti=3, then it is followed by integer qi (1≤qi≤n).
For each third type operation print value aqi. Print the values in the order, in which the corresponding queries follow in the input.