Sereja 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_{v}_{i} = 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_{q}_{i}. 

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_{q}_{i}. 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

Difficulty: interview

Starter code:

Solutions:
import sys
n,m=list(map(int,sys.stdin.readline().split()))

L=list(map(int,sys.stdin.readline().split()))
c=0
Ans=""
for i in range(m):
    x=list(map(int,sys.stdin.readline().split()))
    if(x[0]==1):
        L[x[1]-1]=x[2]-c
    elif(x[0]==2):
        c+=x[1]
    else:
        Ans+=str(L[x[1]-1]+c)+"\n"
sys.stdout.write(Ans)


##n, m = [10,11]
##a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
##s = [[3, 2],
##[3, 9],
##[2, 10],
##[3, 1],
##[3, 10],
##[1, 1, 10],
##[2, 10],
##[2, 10],
##[3, 1],
##[3, 10],
##[3, 9]]

n,m = [int(x) for x in input().split(' ')]
a = [int(x) for x in input().split(' ')]

s = []
for i in range(m):
    s.append( [int(x) for x in input().split(' ')] )


add = 0
for l in s:
    if l[0] == 1:
        v,x = int(l[1]), int(l[2])
        a[v-1] = x-add
    elif l[0] == 2:
        y = int(l[1])
        add += y
    elif l[0] == 3:
        print(a[int(l[1])-1]+add)


N,M = tuple(int(i) for i in input().split())
A = list(int(i) for i in input().split())
AOE = 0
out = ""
for m in range(M):
	val = tuple(int(i) for i in input().split())
	if(val[0]==1):
		ind = val[1]
		x = val[2]
		A[ind-1]=x-AOE
	elif(val[0]==2):
		AOE += val[1]
	elif(val[0]==3):
		out += str(A[val[1]-1]+AOE) + "\n"
print(out,end="")


def main():
    n, m = list(map(int, input().split()))
    aa = list(map(int, input().split()))
    delta, res = 0, []
    for _ in range(m):
        l = list(map(int, input().split()))
        if l[0] == 1:
            aa[l[1] - 1] = (l[2], delta)
        elif l[0] == 2:
            delta += l[1]
        else:
            x = aa[l[1] - 1]
            res.append(str((x[0] - x[1] if type(x) is tuple else x) + delta))
    print('\n'.join(res))


def __starting_point():
    main()

__starting_point()

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
res = []
total_sum = 0

for i in range(m):
    data = list(map(int, input().split()))
    if data[0] == 1:
        a[data[1] - 1] = data[2] - total_sum
    else:
        if data[0] == 2:
            total_sum += data[1]
        else:
            res.append(str(a[data[1] - 1] + total_sum))

print('\n'.join(res))


def go():
    n, m = (int(i) for i in input().split(' '))
    a = [int(i) for i in input().split(' ')]
    keep = 0
    o = ''
    for i in range(m):
        data = tuple(int(i) for i in input().split(' '))
        if data[0] == 1:
            a[data[1] - 1] = data[2] - keep
        elif data[0] == 2:
            keep += data[1]
        elif data[0] == 3:
            o += '{}\n'.format(a[data[1] - 1] + keep)
    return o

print(go())


n,q=list(map(int,input().split()))
a=list(map(int, input().split()))
b=0
s=''
for i in range(q):
    l=list(map(int, input().split()))
    if l[0]==3:
        s+=str(a[l[1]-1]+b)+'\n'
    elif l[0]==2:
        b+=l[1]
    elif l[0]==1:
        a[l[1]-1]= l[2]-b
print(s)


n,m=map(int,input().split())
l=list(map(int,input().split()))
l=[0]+l
l1=[]
for i in range(m):
	l1+=[list(map(int,input().split()))]
k=0
for i in l1:

	if i[0]==1:
		l[i[1]]=i[2]
		
		l[i[1]]-=k
	elif i[0]==2:
		k+=i[1]

	else:
		print(l[i[1]]+k)

n, m = list(map(int, input().split()))
arr = [int(i) for i in input().split()]
res, s = 0, ""
for i in range(m):
    b = [int(x) for x in input().split()]
    if b[0] == 1:
        arr[b[1] - 1] = b[2] - res
    elif b[0] == 2:
        res += b[1]
    else:
        s += str(arr[b[1] - 1] + res) + '\n'
print(s)


# coding: utf-8

from sys import stdin

N, M = list(map(int, input().split()))

A = [int(a) for a in stdin.readline().split()]

globalIncreaser = 0

for i in range(M):
    op = [int(a) for a in stdin.readline().split()]
    opcode = op[0]

    if opcode == 1:
        opcode, v, x = op
        A[v - 1] = x - globalIncreaser

    elif opcode == 2:
        opcode, y = op
        globalIncreaser += y

    elif opcode == 3:
        opcode, q = op
        print(A[q - 1] + globalIncreaser)


##   int(input())
n, m= map(int,input().split())
a = list(map(int,input().split()))
tot = 0
rs = []
for i in range(m):
    t = list(map(int,input().split()))
    if t[0] == 1:
        v = t[1]
        x = t[2]
        a[v - 1] = x - tot
    if t[0] == 2:
        y = t[1]
        tot += y
    if t[0] == 3:
        q = t[1]
        rs.append(str(a[q - 1] + tot))
print('\n'.join(rs))

import sys

n,m = sys.stdin.readline().split()
n = int(n)
m = int(m)

while True:
    num_arr = [int(i) for i in sys.stdin.readline().split(' ')]
    operation_arr = []
    last_sum = 0
    change_map = {}
    for i in range(0,m):
        operation = sys.stdin.readline().split(' ')
        id = int(operation[0])
        if id == 1:
            idx, value = int(operation[1]), int(operation[2])
        else:
            value = int(operation[1])

        if id == 1:
            operation_arr.append(last_sum)
            change_map[idx - 1] = i
            num_arr[idx - 1] = value
        elif id == 2:
            operation_arr.append(value + last_sum)
            last_sum += value
        elif id == 3:
            value -= 1
            operation_arr.append(last_sum)
            if value in change_map:
                print(num_arr[value] + last_sum - operation_arr[change_map[value]])
            else:
                print(num_arr[value] + last_sum)


    nm = sys.stdin.readline().split()
    if not nm:
        break
    else:
        n,m = nm
        n = int(n)
        m = int(m)


import sys

n, m = [int(x) for x in sys.stdin.readline().split()]
a = [int(x) for x in sys.stdin.readline().split()]
increase = 0

for i in range(m):
    op = [int(x) for x in sys.stdin.readline().split()]
    t = op[0] # type of operation
    if t == 1:
        v = op[1]
        x = op[2]
        a[v-1] = x - increase
    elif t == 2:
        y = op[1]
        increase += y
    elif t == 3:
        q = op[1]
        print(a[q-1] + increase)


x,k = input().split()
x = int(x)
k = int(k)

a = list(map(int,input().split()))
b = []
aumento = 0

for i in range(k):
    y = list(map(int, input().split()))
    if(y[0] == 1):
        a[y[1]-1] = y[2] - aumento
    elif(y[0] == 2):
        aumento += y[1]
    else:
        b.append(str(a[y[1]-1] + aumento))
print('\n'.join(b))


values = [*list(map(int, input().split()))]
n, m = values 
array = [*list(map(int, input().split()))]
ad = 0
result = []
for i in range(m):
    op = [*list(map(int, input().split()))]
    if op[0] == 1:
        index = op[1]-1
        array[index] = op[2] - ad
    if op[0] == 2:
        ad += op[1]
    if op[0] == 3:
        index = op[1]-1
        result.append(str(array[index]+ad))
 
print('\n'.join(result))


values = [*list(map(int, input().split()))]
n, m = values 
array = [*list(map(int, input().split()))]
ad = 0
result = []
for i in range(m):
    op = [*list(map(int, input().split()))]
    if op[0] == 1:
        index = op[1]-1
        array[index] = op[2] - ad
    if op[0] == 2:
        ad += op[1]
    if op[0] == 3:
        index = op[1]-1
        result.append(str(array[index]+ad))
 
print('\n'.join(result))


firstLine = list(map(int, input().split()))
array = list(map(int, input().split()))

arraySize = firstLine[0]
numOperations = firstLine[1]
totalSum = 0
s = ""

for i in range(numOperations):
    command = list(map(int, input().split()))
    op = command[0]
    param1 = command[1]

    if(op == 1):
      array[param1 - 1] = command[2] - totalSum
    elif(op == 2):
      totalSum += param1
    else:
      s += str(array[param1 - 1] + totalSum) + '\n'

print(s)


firstLine = list(map(int, input().split()))
array = list(map(int, input().split()))

arraySize = firstLine[0]
numOperations = firstLine[1]
totalSum = 0
s = ""

for i in range(numOperations):
    command = list(map(int, input().split()))
    op = command[0]
    param1 = command[1]

    if(op == 1):
      array[param1 - 1] = command[2] - totalSum
    elif(op == 2):
      totalSum += param1
    else:
      s += str(array[param1 - 1] + totalSum) + '\n'

print(s)