from sys import stdin
import heapq
d = dict()

class HeapDict:
    def __init__(self):
        self.h=[]
        self.d=dict()

    def insert(self,x):
        heapq.heappush(self.h,x)
        if x not in self.d:
            self.d[x]=1
        else:
            self.d[x]+=1

    def erase(self,x):
        if x not in self.d or self.d[x]==0:
            print(x,"is not in HeapDict")
            exit()
        else:
            self.d[x]-=1

        while len(self.h)!=0:
            if self.d[self.h[0]]==0:
                heapq.heappop(self.h)
            else:
                break

    def is_exist(self,x):
        if x in self.d and self.d[x]!=0:
            return True
        else:
            return False

    def is_empty(self):
        if self.h:
            return False
        else:
            return True

    def get_min(self):
        return self.h[0]

n, m, *indata = map(int, stdin.read().split())
numlist = [0 for i in range(m+1)]
numset = HeapDict()
for i in range(m):
    a = indata[i]
    numlist[i+1] = a
    if not (numset.is_exist(-a)):
        d[-a] = HeapDict()
    d[-a].insert(-i-1)
    numset.insert(-a)

q = indata[m]

offset = m+1
for i in range(q):
    t, x, y  = indata[offset + 3*i],indata[offset + 3*i+1],indata[offset + 3*i+2]
    if t == 1:
        kari = numlist[x]
        d[-kari].erase(-x)
        numset.erase(-kari)
        kari += y
        numlist[x] += y
        if not (numset.is_exist(-kari)):
            d[-kari] = HeapDict()
        numset.insert(-kari)
        d[-kari].insert(-x)
    elif t == 2:
        kari = numlist[x]
        d[-kari].erase(-x)
        numset.erase(-kari)
        kari -= y
        numlist[x] -= y
        if not (numset.is_exist(-kari)):
            d[-kari] = HeapDict()
        numset.insert(-kari)
        d[-kari].insert(-x)
    else:
        maxnum = numset.get_min()
        ans = - d[maxnum].get_min()
        print("{}".format(ans))