import sys readline=sys.stdin.readline class AVL_Node_dict: """ノード Attributes: key (any): ノードのキー。比較可能なものであれば良い。(1, 4)などタプルも可。 val (any): ノードの値。 left (Node): 左の子ノード。 right (Node): 右の子ノード。 bias (int): 平衡度。(左部分木の高さ)-(右部分木の高さ)。 size (int): 自分を根とする部分木の大きさ """ def __init__(self,parent,key,value): self.parent=parent self.key=key self.value=value self.left=None self.right=None self.bias=0 self.size=1 class AVLTree_dict: def __init__(self): self.root=None def Rotate_Left(self,node): node_right=node.right node_right.size=node.size node.size-=1 if node_right.right!=None: node.size-=node_right.right.size if node_right.bias==-1: node_right.bias=0 node.bias=0 else: #assert node_right.bias==0 node_right.bias=1 node.bias=-1 node.right=node_right.left node_right.left=node return node_right def Rotate_Right(self,node): node_left=node.left node_left.size=node.size node.size-=1 if node_left.left!=None: node.size-=node_left.left.size if node_left.bias==1: node_left.bias=0 node.bias=0 else: #assert node_left.bias==0 node_left.bias=-1 node.bias=1 node.left=node_left.right node_left.right=node return node_left def Rotate_Left_Right(self,node): node_left=node.left node_left_right=node_left.right #assert node.bias==2 #assert node_left.bias==-1 #assert node_left_right.bias in (-1,0,1) node_left_right.size=node.size node.size-=node_left.size if node_left_right.right!=None: node.size+=node_left_right.right.size node_left.size-=1 if node_left_right.right!=None: node_left.size-=node_left_right.right.size node_left.right=node_left_right.left node_left_right.left=node_left node.left=node_left_right.right node_left_right.right=node self.Update_Bias_Double(node_left_right) return node_left_right def Rotate_Right_Left(self,node): node_right=node.right node_right_left=node_right.left #assert node.bias==-2 #assert node_right.bias==1 #assert node_right_left.bias in (-1,0,1) node_right_left.size=node.size node.size-=node_right.size if node_right_left.left!=None: node.size+=node_right_left.left.size node_right.size-=1 if node_right_left.left!=None: node_right.size-=node_right_left.left.size node_right.left=node_right_left.right node_right_left.right=node_right node.right=node_right_left.left node_right_left.left=node self.Update_Bias_Double(node_right_left) return node_right_left def Update_Bias_Double(self,node): #assert node.right.bias*node.left.bias==-2 #assert node.right.bias>0 if node.bias==1: node.right.bias=-1 node.left.bias=0 elif node.bias==-1: node.right.bias=0 node.left.bias=1 else: node.right.bias=0 node.left.bias=0 node.bias=0 def __getitem__(self,key): v=self.root while v!=None: if keykey: if retu==None or retu[0]>v.key: retu=(v.key,v.value) v=v.left else: v=v.right return retu def Bisect_Left(self,key): retu=None v=self.root while v!=None: if v.key