import sys sys.setrecursionlimit(10**7) def ii(): return int(input()) def mi(d=0): return map(lambda x:int(x)-d,input().split()) ################################################ class AVLTree: def __init__(self,debugmode=False): self.nodes = {} self.keys = set([]) self.debugmode = debugmode self.changes = [] self.changeKeys = set([]) #ノードの追加。 def add(self,key,count=1): if len(self.keys): if not key in self.keys: self.root,new_node = self.root.add(key,count) self.nodes[key] = new_node self.keys.add(key) else: self.debugLog(f"node{key} += {count}") self.nodes[key].count += count node:AVLTree.Node = self.nodes[key] while node: node.calcHeight() node = node.parent if self.debugmode: self.root.check() else: self.root = AVLTree.Node(key,count,AVLTree.NONE) self.keys.add(key) self.nodes[key] = self.root def remove(self,key): if key in self.keys: target = self.nodes[key] if target.count > 1: target.count -= 1 while target: target.calcHeight() target = target.parent self.debugLog(f"decline {key}") else: self.debugLog(f"delete {key}") ch,rep = target,target if target.left: if target.right: rep = target.right.getBiggerMin(-10**9+1) self.debugLog(f"swap {target.key} to {rep.key}") ch = rep if target.right != rep: self.changeParent(rep,rep.right) rep.right = target.right target.right.parent = rep ch = rep.parent rep.left = target.left target.left.parent = rep # self.root.check() else: rep = target.left ch = target.parent else: ch = target.parent if target.right: rep = target.right else: rep = AVLTree.NONE self.changeParent(target,rep) self.root = self.checkBalances(ch) self.keys.remove(key) del self.nodes[key] if self.debugmode: self.root.check() def checkBalances(self,node): while node: node.calcHeight() np = node.parent if np: if np < node: np.right = node.checkBalance() else: np.left = node.checkBalance() else: return node.checkBalance() node = np def changeParent(self,f,t): p = f.parent if not p: self.debugLog("root delete!") self.root = t t.parent = AVLTree.NONE return else: if p < f: p.right = t else: p.left = t if t: t.parent = p def debugLog(self,string): if self.debugmode: print(string) #ノードをkey順に並べたとき、指定したノードの左右のノードを返す def getNexts(self,key): if key in self.keys: s = self.root.getSmallerMax(key) b = self.root.getBiggerMin(key) return s,b def __getitem__(self,index): if len(self) > index: i = 0 node = self.root while True: # print(node.key,i) leftcount = node.left.childCount + i + node.left.count if leftcount <= index < leftcount + node.count: return node elif leftcount + node.count <= index: i += leftcount + node.count - i node = node.right else: node = node.left else: return AVLTree.NONE def __len__(self): return self.root.childCount + self.root.count def sort(self): # print(self.changeKeys) # print(self.changes) for k in self.changeKeys: node,x = self.changes[k] self.debugLog(f"remove{node.key},add{x}") self.remove(node.key) self.add(x) self.changeKeys.clear() def getValue(self,k): if k in self.changeKeys: return self.changes[k][1] else: return self[k] #ノードを表すクラス class Node: def __init__(self,key,count,parent): self.key = key self.count = count self.left = AVLTree.NONE self.right = AVLTree.NONE self.height:int = 1 self.parent = parent self.childCount = 0 #子ノードを追加する処理。追加した後、バランスを計算して必要なら回転し、回転後の親ノードと追加されたノードを返す。 def add(self,key,count=1): ret = AVLTree.NONE if key < self: if self.left: self.left,ret = self.left.add(key,count) else: self.left = AVLTree.Node(key,count,self) ret = self.left if key > self: if self.right: self.right,ret = self.right.add(key,count) else: self.right = AVLTree.Node(key,count,self) ret = self.right self.calcHeight() return self.checkBalance(),ret def getBalance(self): return self.left.height - self.right.height # バランスを計算し、傾いているなら回転させる。回転した後の親ノードを返す。 def checkBalance(self): balance = self.getBalance() ret = self if balance < -1: ret = self.swapLeft() elif balance > 1: ret = self.swapRight() return ret #回転処理。回転後に自分の位置に来るノードを返す。 def swapRight(self): if self.left.getBalance() <= -1: self.left = self.left.swapLeft() left = self.left self.parent,left.parent = left,self.parent self.left,left.right = left.right,self self.left.parent = self self.calcHeight() left.calcHeight() return left def swapLeft(self): if self.right.getBalance() >= 1: self.right = self.right.swapRight() right = self.right self.parent,right.parent = right,self.parent self.right,right.left = right.left,self self.right.parent = self self.calcHeight() right.calcHeight() return right def calcHeight(self): self.height = max(self.left.height,self.right.height)+1 self.childCount = self.left.childCount + self.right.childCount + self.left.count + self.right.count def getSmallerMax(self,x=10**9+1): if self > x: if self.left: return self.left.getSmallerMax(x) else: return AVLTree.NONE elif self < x: if self.right: r = self.right.getSmallerMax(x) return r if r else self else: return self def getBiggerMin(self,x=-10**9+1): if self < x: if self.right: return self.right.getBiggerMin(x) else: return AVLTree.NONE elif self > x: if self.left: l = self.left.getBiggerMin(x) return l if l else self else: return self def check(self,flag=False): q = [self] i = 0 while q: nq = [] if flag: print(*map(lambda x:(str(x),x.childCount,str(x.parent),str(x.left),str(x.right)),q)) else: print(*map(str,q)) f = False for qq in q: nq.append(qq.left if qq.left else AVLTree.NONE) f |= bool(qq.left) nq.append(qq.right if qq.right else AVLTree.NONE) f |= bool(qq.right) q = nq i += 1 if not f or i > 5: break def __str__(self): return str(self.key) def __lt__(self,other): if type(other) == AVLTree.Node: return self.key < other.key elif type(other) == int: return self.key < other else: print(other,"?") raise TypeError def __gt__(self,other): if type(other) == AVLTree.Node: return self.key > other.key elif type(other) == int: return self.key > other else: print(other,"?") raise TypeError class Null: def __init__(self): self.key = -1 self.count = 0 self.left = None self.right = None self.parent = None self.height = 0 self.childCount = 0 def __bool__(self): return False def __str__(self): return "x" NONE = Null() n,q = mi() a = list(mi()) tree = AVLTree() f = False for aa in a: tree.add(aa) tree.changes.append(-1) for _ in range(q): query = input() if query[0] == "1": _,k,x = map(int,query.split()) # print(f"change {tree[k-1].key} to {x}") tree.changes[k-1] = (tree[k-1],x) tree.changeKeys.add(k-1) elif query[0] == "2": f = True tree.sort() else: _,k = map(int,query.split()) if not f: print(a[k-1]) else: print(tree.getValue(k-1).key)