Sereja has got an array, consisting of *n* integers, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. 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*<sub class="lower-index">*i*</sub>-th array element equal to *x*<sub class="lower-index">*i*</sub>. In other words, perform the assignment *a*<sub class="lower-index">*v*<sub class="lower-index">*i*</sub></sub> = *x*<sub class="lower-index">*i*</sub>. 1.  Increase each array element by *y*<sub class="lower-index">*i*</sub>. In other words, perform *n* assignments *a*<sub class="lower-index">*i*</sub> = *a*<sub class="lower-index">*i*</sub> + *y*<sub class="lower-index">*i*</sub> (1 ≤ *i* ≤ *n*). 1.  Take a piece of paper and write out the *q*<sub class="lower-index">*i*</sub>-th array element. That is, the element *a*<sub class="lower-index">*q*<sub class="lower-index">*i*</sub></sub>. 
Help Sereja, complete all his operations.
The first line contains integers *n*, *m* (1 ≤ *n*, *m* ≤ 10<sup class="upper-index">5</sup>). The second line contains *n* space-separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — 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*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 3) that represents the operation type. If *t*<sub class="lower-index">*i*</sub> = 1, then it is followed by two integers *v*<sub class="lower-index">*i*</sub> and *x*<sub class="lower-index">*i*</sub>, (1 ≤ *v*<sub class="lower-index">*i*</sub> ≤ *n*, 1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>). If *t*<sub class="lower-index">*i*</sub> = 2, then it is followed by integer *y*<sub class="lower-index">*i*</sub> (1 ≤ *y*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">4</sup>). And if *t*<sub class="lower-index">*i*</sub> = 3, then it is followed by integer *q*<sub class="lower-index">*i*</sub> (1 ≤ *q*<sub class="lower-index">*i*</sub> ≤ *n*).
def solution(n , a , m , operations):
        index = list()
        index2 = list()
        index3 = dict()
        count = 0
        for i in operations:
                t = i[0]

                if t == 1:
                        v = i[1]
                        x = i[2]
                        index.append(v - 1)
                        index3[v - 1] = (count , x)
                elif t == 2:
                        y = i[1]
                        index2.append(y)
                        count += 1
                else:
                        q = i[1]
                        if q - 1 in index:
                                temp = index3[q - 1]
                                total = sum(index2[temp[0]:]) + temp[1]
                        else:
                                total = sum(index2) + a[q - 1]
                        print (total)


if __name__ == "__main__":
        temp = list(map(int , input().rstrip().split()))
        n = temp[0]
        m = temp[1]

        a = list(map(int , input().rstrip().split()))

        operations = list()
        for i in range(m):
                temp = tuple(map(int , input().rstrip().split()))
                operations.append(temp)

        
        solution(n , a , m , operations)
