Problem:

Priority Queue

  Priority queue is a container of elements which the element with the highest priority should be extracted first.

  For $n$ priority queues $Q_i$ ($i = 0, 1, ..., n-1$) of integers, perform a sequence of the following operations.

  
insert($t$, $x$): Insert $x$ to $Q_t$.

  
getMax($t$): Report the maximum value in $Q_t$. If $Q_t$ is empty, do nothing.

  
deleteMax($t$): Delete the maximum element from $Q_t$. If $Q_t$ is empty, do nothing.

In the initial state, all queues are empty.

Input

  The input is given in the following format.

$n \; q$
$query_1$
$query_2$
:
$query_q$

Each query $query_i$ is given by

0 $t$ $x$

or

1 $t$

or

2 $t$

  where  the first digits 0, 1 and 2 represent insert, getMax and deleteMax operations respectively.

Output

  For each getMax operation, print an integer in a line.

Constraints

  
$1 \leq n \leq 1,000$

  
$1 \leq q \leq 200,000$

  
$-1,000,000,000 \leq x \leq 1,000,000,000$

Sample Input 1

2 10
0 0 3
0 0 9
0 0 1
1 0
2 0
1 0
0 0 4
1 0
0 1 8
1 1

Sample Output 1

9
3
4
8



Sample input:
2 10
0 0 3
0 0 9
0 0 1
1 0
2 0
1 0
0 0 4
1 0
0 1 8
1 1


Sample output:
9
3
4
8

Submission status: Accepted

Solution code:
import heapq
n, q = map(int, input().split())
Q = [[] for i in range(n)]
queries = list()
for i in range(q):
    queries.append(list(map(int, input().split())))
for query in queries:
    if query[0] == 0:
        heapq.heappush(Q[query[1]], -query[2])
    elif query[0] == 1:
        if Q[query[1]]:
            print(-Q[query[1]][0])
    elif query[0] == 2:
        if Q[query[1]]:
            heapq.heappop(Q[query[1]])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import heapq

N,Q = map(int,input().split())

H = [[] for _ in range(N)]

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0] == 0:
        heapq.heappush(H[q[1]],-q[2])
    elif q[0] == 1:
        if H[q[1]]:
            print(-H[q[1]][0])
    else:
        if H[q[1]]:
            heapq.heappop(H[q[1]])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def main():
    n, q = map(int, input().split())
    Qt = [list() for _ in range(n)]
    for _ in range(q):
        para = [int(a) for a in input().split()]

        if para[0] == 0:
            heappush(Qt[para[1]], -(para[2]))
        if para[0] == 1:
            if len(Qt[para[1]]) != 0:
                m = heappop(Qt[para[1]])
                print(-m)
                heappush(Qt[para[1]], m)
        if para[0] == 2:
            if len(Qt[para[1]]) != 0:
                heappop(Qt[para[1]])
main()

Submission status: Accepted

Solution code:
import heapq


class TwoDimPriorityQueue():
    def __init__(self, num_queues):
        self.queues = [[] for i in range(0, num_queues, 1)]

    def insert(self, t, x):
        heapq.heappush(self.queues[t], (-1) * x)
        return self

    def getMax(self, t):
        if len(self.queues[t]) > 0:
            return (-1) * self.queues[t][0]
        return None

    def deleteMax(self, t):
        if len(self.queues[t]) > 0:
            heapq.heappop(self.queues[t])
        return self


num_queues, num_op = map(int, input().split(' '))
queues = TwoDimPriorityQueue(num_queues)

for op in range(0, num_op):
    op = tuple(map(int, input().split(' ')))
    if op[0] == 0:
        queues.insert(op[1], op[2])
    elif op[0] == 1:
        max_number = queues.getMax(op[1])
        if max_number != None:
            print(f'{max_number}')
    elif op[0] == 2:
        queues.deleteMax(op[1])

Submission status: Accepted

Solution code:
#%%二分探索?めんどくせぇ%% TLEしました。
import bisect

n,q=[int(i) for i in input().split(" ")]

Q=[[] for i in range(n)]

for _ in range(q):
    query=[int(j) for j in input().split(" ")]
    if query[0]==0:
        index=bisect.bisect_left(Q[query[1]],query[2])
        Q[query[1]].insert(index,query[2])
    elif query[0]==1:
        if len(Q[query[1]])>0:
            print(Q[query[1]][-1])
    else:
        if len(Q[query[1]])>0:
            Q[query[1]].pop(-1)

Submission status: Accepted

Solution code:
import heapq
n, q = [int(x) for x in input().split()]
L = [ [] for _ in range(n)]
for _ in range(q):
    c, t, x = [int(x) for x in (input()+ " 0").split()][:3]
    if c == 0:
        heapq.heappush(L[t],-x)
    elif c == 1:
        try:
            print(-L[t][0])
        except IndexError:
            pass
    else:
        try:
            heapq.heappop(L[t])
        except IndexError:
            pass

Submission status: Accepted

Solution code:
import sys
import heapq

n, q = map(int, input().split())

Q = [[] for _ in range(n)]
ans = []
heapq.heapify(Q)
for query in (line.split() for line in sys.stdin):
    t = int(query[1])
    if query[0] == '0':
        u = int(query[2])
        heapq.heappush(Q[t], -u)
    elif query[0] == '1' and Q[t]:
        ans.append(-Q[t][0])
    elif query[0] == '2' and Q[t]:
        heapq.heappop(Q[t])

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
#既存のもの頼み
#最小値でなく最大値なのでマイナスつける
import heapq

n, q = map(int, input().split( ))
Q = [[] for _ in range(n)]
for _ in range(q):
    cmd = list(map(int, input().split( )))
    if cmd[0] == 0:
        t = cmd[1]
        x = cmd[2]
        heapq.heappush(Q[t],-x)
    elif cmd[0] == 1:
        t = cmd[1]
        if Q[t]:##
            mx = - heapq.heappop(Q[t])
            print(mx)
            heapq.heappush(Q[t],-mx)
    else:##
        t = cmd[1]
        if Q[t]:
            heapq.heappop(Q[t])

Submission status: Accepted

Solution code:
import bisect

n, q = map(int, input().split())
Q = [[] for i in range(n)]

for i in range(q):
    query = list(map(int, input().split()))
    
    if query[0] == 0: bisect.insort_left(Q[query[1]], query[2])
    elif query[0] == 1 and len(Q[query[1]]): print(Q[query[1]][-1])
    elif query[0] == 2 and len(Q[query[1]]): Q[query[1]].pop(-1)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush


if __name__ == "__main__":
    heap_num, query_num = map(lambda x: int(x), input().split())
    heaps = [[] for _ in range(heap_num)]  # type: ignore
    for heap in heaps:
        heapify(heap)

    for _ in range(query_num):
        op, *value = map(lambda x: int(x), input().split())
        heap = heaps[value[0]]
        if (0 == op):
            heappush(heap, -value[1])
        elif (1 == op):
            if (0 != len(heap)):
                print(-heap[0])
        elif (2 == op):
            if (0 != len(heap)):
                heappop(heap)
        else:
            pass

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    n, q = map(int, f_i.readline().split())
    
    from heapq import heappop, heappush
    Q = [[] for i in range(n)]
    
    ans = []
    
    for op in (line.split() for line in f_i):
        op_type = op[0]
        t = int(op[1])
        pq_t = Q[t]
        if op_type == '0':
            heappush(pq_t, -int(op[2]))
        elif pq_t:
            if op_type == '1':
                ans.append(-pq_t[0])
            else:
                heappop(pq_t)
    print('\n'.join(map(str, ans)))

solve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappop, heappush
n = int(sys.stdin.readline().split()[0])
A = defaultdict(list)
ans = []
for query in sys.stdin:
    if query[0] == '0':
        t, x = query[2:].split()
        heappush(A[t], -int(x))
    elif query[0] == '1':
        if A[query[2:-1]]:
            ans.append(f'{-A[query[2:-1]][0]}' + '\n')
    else:
        if A[query[2:-1]]:
            heappop(A[query[2:-1]])
sys.stdout.writelines(ans)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
from collections import defaultdict
from heapq import heappush, heappop

n, q = map(int,stdin.readline().split())
queries = stdin.readlines()
A = defaultdict(list)
ans = []

#count = 0
for query in queries:
    #print(count)
    #count += 1
    query = query.split()
    if query[0] == '0':
        heappush(A[int(query[1])], -int(query[2]))
    elif query[0] == '1':
        index = int(query[1])
        if len(A[index]) > 0:
            print(-A[index][0])
    else:
        index = int(query[1])
        if len(A[index]) > 0:
            heappop(A[index])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Basic Data Structures - Priority Queue
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_2_C&lang=jp

"""
from heapq import heappop, heappush

n, q = map(int, input().split())
pq = [[] for _ in range(n)]
for _ in range(q):
    op, t, x = (input() + ' 1').split()[:3]
    if op == '0':
        heappush(pq[int(t)], int(x)*-1)
    elif op == '1':
        if pq[int(t)]:
            print(pq[int(t)][0]*-1)
    else:
        if pq[int(t)]:
            heappop(pq[int(t)])

Submission status: Accepted

Solution code:
import heapq
n, queries = map(int, input().split())
Q = [[] for i in range(n)]

for i in range(queries):
    q, t, *x = map(int, input().split())
    if q == 0: heapq.heappush(Q[t], -x[0])
    elif q == 1 and Q[t]: print(-Q[t][0])
    elif q == 2 and Q[t]: heapq.heappop(Q[t])

Submission status: Accepted

Solution code:
import bisect



n, q = map(int, input().split())

Q = [[] for _ in range(n)]


for _ in range(q):

    command, *list_num = input().split()

    t = int(list_num[0])

    if   command == "0":
        # insert(t, x)
        x = int(list_num[1])
        bisect.insort(Q[t], x)
    elif command == "1":
        # getMax(t)
        if Q[t]:
            print(Q[t][-1])
    elif command == "2":
        # deleteMax(t)
        if Q[t]:
            del Q[t][-1]
    else:
        raise

Submission status: Accepted

Solution code:
from heapq import *

n, q = map(int, input().split())
box = [[] for i in range(n)]
for _ in range(q):
    a, b, *c = map(int, input().split())
    if a == 0:
        heappush(box[b],-c[0])
    elif a == 1 and box[b]:
        print(-box[b][0])
    else:
        if box[b]:heappop(box[b])

Submission status: Accepted

Solution code:
import heapq as hq
n,q = map(int,input().split())
a = [[] for i in range(n)]

for i in range(q):
	k = list(map(int,input().split()))
	if k[0] == 0:
		hq.heappush(a[k[1]],-k[2])
	elif k[0] == 1:
		a[k[1]] and print(-a[k[1]][0])
	else:
		a[k[1]] and hq.heappop(a[k[1]])

Submission status: Accepted

Solution code:
import heapq
n,q = map(int, input().split())
S = [[] for i in range(n)]

for i in range(q):
    a = input().split()
    t = int(a[1])
    
    if a[0] == '0':
        heapq.heappush(S[t],-int(a[2]))
    elif a[0] == '1' and S[t]:
        print(-S[t][0])
    elif a[0] == '2' and S[t]:
        heapq.heappop(S[t])

Submission status: Accepted

Solution code:
import heapq

def main():       
    n,q=(int(x) for x in input().split())
    Q=[[] for i in range(n)]
    for i in range(q):
        query=list(map(int,input().split()))
        if query[0]==0:
            heapq.heappush(Q[query[1]],-1*query[2])
        elif query[0]==1:
            if len(Q[query[1]])!=0:
                print(-1*Q[query[1]][0])
        else:
            if len(Q[query[1]])!=0:
                heapq.heappop(Q[query[1]])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n,q = map(int,input().split())
Q = [[] for i in range(n)]

for i in range(q):
    query = [k for k in map(int,input().split())]

    if query[0] == 0:
       heapq.heappush(Q[query[1]],-query[2])
    elif query[0] == 1:
        try:
            print(-Q[query[1]][0])
        except:
            pass
    elif query[0] == 2:
        try:
            heapq.heappop(Q[query[1]])
        except:
            pass

Submission status: Accepted

Solution code:
import sys
import heapq
n, q = map(int, input().split())

queues = {str(i): [] for i in range(n)}

lines = sys.stdin.readlines()
for i in range(q):
    query, *arg = lines[i].split()
    if query == '0':    # insert t x
        heapq.heappush(queues[arg[0]], -int(arg[1]))
    elif query == '1':  # getMax
        if len(queues[arg[0]]):
            print(-queues[arg[0]][0])
    elif query == '2':  # deleteMax
        if len(queues[arg[0]]):
            heapq.heappop(queues[arg[0]])
    else:
        raise AssertionError

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_2_C&lang=jp
# Priority Queue

from collections import deque
import sys
input = sys.stdin.readline
import heapq

def loop_proc():
    (n1,n2) = map(int,input().split())
    wl =[]
    for i in range(n1):
        wl.append(list())
    for i in range(n2):
        l = list(map(int,input().split()))  
        if (l[0] == 0 ):
            n = l[1]
            d = l[2]
            heapq.heappush(wl[n],-1 * d)
        elif (l[0] == 1 ):
            if ( len(wl[l[1]]) != 0 ):
                tl = wl[l[1]]
                a = heapq.heappop(tl) 
                heapq.heappush(tl,a) 
                print (int(a) * -1 )
        elif (l[0] == 2 ):
            if ( len(wl[l[1]]) != 0 ):
                tl = wl[l[1]]
                heapq.heappop(tl)  


if __name__ == '__main__':
    loop_proc()
#   import cProfile
#   pr = cProfile.Profile()
#   pr.runcall(loop_proc)
#   pr.print_stats()

Submission status: Accepted

Solution code:
import heapq

n, q = map(int, input().split())
stack = [[] for _ in range(n)]
heapq.heapify(stack)

for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 0:
        heapq.heappush(stack[query[1]], -query[2])
    elif query[0] == 1:
        if stack[query[1]] == []:
            pass
        else:
            print(-stack[query[1]][0])
    elif query[0] == 2:
        if stack[query[1]] == []:
            pass
        else:
            heapq.heappop(stack[query[1]])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
readline = open(0).readline
writelines = open(1, 'w').writelines
N, Q = map(int, readline().split())
ans = []
A = [[] for i in range(N)]
def push(t, x):
    heappush(A[t], -x)
def get_max(t):
    A[t] and ans.append("%d\n" % -A[t][0])
def delete_max(t):
    A[t] and heappop(A[t])

C = [push, get_max, delete_max].__getitem__
for i in range(Q):
    t, *a=map(int, readline().split())
    C(t)(*a)
writelines(ans)

Submission status: Accepted

Solution code:
from __future__ import print_function
import sys,heapq
n,q=map(int,sys.stdin.readline().split())
a=[[] for _ in range(n)]
for _ in range(q):
  g=list(map(int,sys.stdin.readline().split()))
  if g[0]==0:
    heapq.heappush(a[g[1]],-g[2])
  elif g[0]==1:
    a[g[1]] and print(-a[g[1]][0])
  else:
    a[g[1]] and heapq.heappop(a[g[1]])

Submission status: Accepted

Solution code:
from __future__ import print_function
import sys,heapq
n,q=map(int,sys.stdin.readline().split())
a=[[] for _ in range(n)]
for _ in range(q):
  g=map(int,sys.stdin.readline().split())
  if g[0]==0:
    heapq.heappush(a[g[1]],-g[2])
  elif g[0]==1:
    a[g[1]] and print(-a[g[1]][0])
  else:
    a[g[1]] and heapq.heappop(a[g[1]])

Submission status: Accepted

Solution code:
import heapq

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        heapq.heappush(a[c[1]],-c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(-a[c[1]][0])
    else:
        if a[c[1]]:
            heapq.heappop(a[c[1]])

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n, q = list(map(int, input().split()))
a = [[] for i in range(n)]
for _ in range(q):
  q = list(map(int, input().split()))
  if q[0]==0:
    heappush(a[q[1]], -1*q[2])
  elif q[0]==1:
    if len(a[q[1]])>0:
      print(-1*a[q[1]][0])
  elif q[0]==2:
    if len(a[q[1]])>0:
      heappop(a[q[1]])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            else:
                j = len(a[c[1]])-1
                while True:
                    if a[c[1]][j-1] < c[2]:
                        a[c[1]].insert(j, c[2])
                        break
                    j -= 1
                    if j == 0:
                        a[c[1]].insert(0, c[2])
                        break
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()

Submission status: Runtime Error

Solution code:
class binaryTree:
    def __init__(self, root = None):
        self.value = root
        self.left = None
        self.right = None

def makeBntr(bnary, num):
    if bnary is None:
        return binaryTree(num)

    elif bnary.value is None:
        return binaryTree(num)

    elif bnary.value < num:
        bnary.left = makeBntr(bnary.left, num)

    else:
        bnary.right = makeBntr(bnary.right, num)

    return bnary

def maxLeaf(bnary):
    if bnary.value is None:
        return 0

    elif bnary.left is not None:
        return maxLeaf(bnary.left)

    else:
        return bnary

def getLeaf(bnary):
    return maxLeaf(bnary).value

def mkBntr(bnary, num):
    if bnary is None:
        return num

    elif bnary.value < num.value:
        bnary.left = mkBntr(bnary.left, num)

    else:
        bnary.right = mkBntr(bnary.right, num)

    return bnary

def toLeft(bnary):
    if bnary.left is None:
        right = bnary.right
        bnary = None
        return bnary, right
    else:
        bnary.left, right = toLeft(bnary.left)
        return bnary, right

def delLeaf(bnary):
    bnary, right = toLeft(bnary)
    return bnary if right is None else mkBntr(bnary, right)



if __name__ == '__main__':
    n, q = input().split()
    n, q = int(n), int(q)
    S = [binaryTree() for i in range(n)]

    for i in range(q):
        query = input().split()
        bnary = S[int(query[1])]
        if query[0] == '0':
            S[int(query[1])] = makeBntr(bnary, int(query[2]))

        else:
            if bnary.value is None:
                pass
            elif query[0] == '1':
                print(getLeaf(bnary))
            else:
                S[int(query[1])] = delLeaf(bnary)

Submission status: Runtime Error

Solution code:
class binaryTree:
    def __init__(self, root = None):
        self.value = root
        self.left = None
        self.right = None

def makeBntr(bnary, num):
    if bnary is None or bnary.value is None:
        return binaryTree(num)

    elif bnary.value is None:
        return binaryTree(num)

    elif bnary.value < num:
        bnary.left = makeBntr(bnary.left, num)

    else:
        bnary.right = makeBntr(bnary.right, num)

    return bnary

def maxLeaf(bnary):
    if bnary.value is None:
        return 0

    elif bnary.left is not None:
        return maxLeaf(bnary.left)

    else:
        return bnary

def getLeaf(bnary):
    return maxLeaf(bnary).value

def mkBntr(bnary, num):
    if bnary is None:
        return num

    elif bnary.value < num.value:
        bnary.left = mkBntr(bnary.left, num)

    else:
        bnary.right = mkBntr(bnary.right, num)

    return bnary

def toLeft(bnary):
    if bnary.left is None:
        right = bnary.right
        bnary = None
        return bnary, right
    else:
        bnary.left, right = toLeft(bnary.left)
        return bnary, right

def delLeaf(bnary):
    bnary, right = toLeft(bnary)
    if bnary is None:
        bnary = binaryTree()
    return bnary if right is None else mkBntr(bnary, right)



if __name__ == '__main__':
    n, q = input().split()
    n, q = int(n), int(q)
    S = [binaryTree() for i in range(n)]
    count = 1
    for i in range(q):
        query = input().split()
        if query[1] != "12":
            continue
        print("---status---")
        print("count:", count)
        count += 1
        print("q[0] = %s, q[1] = %s" %(query[0], query[1]))

        bnary = S[int(query[1])]
        print(bnary.value, bnary.left, bnary.right)print(bnary)
        print()
        if query[0] == '0':
            S[int(query[1])] = makeBntr(bnary, int(query[2]))

        else:
            if bnary.value is None:
                pass
            elif query[0] == '1':
                print(getLeaf(bnary))
            else:
                S[int(query[1])] = delLeaf(bnary)

Submission status: Runtime Error

Solution code:
class binaryTree:
    def __init__(self, root = None):
        self.value = root
        self.left = None
        self.right = None

def makeBntr(bnary, num):
    if bnary is None or bnary.value is None:
        return binaryTree(num)

    elif bnary.value is None:
        return binaryTree(num)

    elif bnary.value < num:
        bnary.left = makeBntr(bnary.left, num)

    else:
        bnary.right = makeBntr(bnary.right, num)

    return bnary

def maxLeaf(bnary):
    if bnary.value is None:
        return 0

    elif bnary.left is not None:
        return maxLeaf(bnary.left)

    else:
        return bnary

def getLeaf(bnary):
    return maxLeaf(bnary).value

def mkBntr(bnary, num):
    if bnary is None:
        return num

    elif bnary.value < num.value:
        bnary.left = mkBntr(bnary.left, num)

    else:
        bnary.right = mkBntr(bnary.right, num)

    return bnary

def toLeft(bnary):
    if bnary.left is None:
        right = bnary.right
        bnary = None
        return bnary, right
    else:
        bnary.left, right = toLeft(bnary.left)
        return bnary, right

def delLeaf(bnary):
    bnary, right = toLeft(bnary)
    if bnary is None:
        bnary = binaryTree()
    return bnary if right is None else mkBntr(bnary, right)



if __name__ == '__main__':
    n, q = input().split()
    n, q = int(n), int(q)
    S = [binaryTree() for i in range(n)]
    for i in range(q):
        query = input().split()

        bnary = S[int(query[1])]
        if query[0] == '0':
            S[int(query[1])] = makeBntr(bnary, int(query[2]))

        else:
            if bnary.value is None:
                pass
            elif query[0] == '1':
                print(getLeaf(bnary))
            else:
                S[int(query[1])] = delLeaf(bnary)

Submission status: Runtime Error

Solution code:
class binaryTree:
    def __init__(self, root = None):
        self.value = root
        self.left = None
        self.right = None

def makeBntr(bnary, num):
    if bnary is None or bnary.value is None:
        return binaryTree(num)

    elif bnary.value is None:
        return binaryTree(num)

    elif bnary.value < num:
        bnary.left = makeBntr(bnary.left, num)

    else:
        bnary.right = makeBntr(bnary.right, num)

    return bnary

def maxLeaf(bnary):
    if bnary.value is None:
        return 0

    elif bnary.left is not None:
        return maxLeaf(bnary.left)

    else:
        return bnary

def getLeaf(bnary):
    return maxLeaf(bnary).value

def mkBntr(bnary, num):
    if bnary is None or bnary.value is None:
        return num

    elif bnary.value < num.value:
        bnary.left = mkBntr(bnary.left, num)

    else:
        bnary.right = mkBntr(bnary.right, num)

    return bnary

def toLeft(bnary):
    if bnary.left is None:
        right = bnary.right
        bnary = None
        return bnary, right
    else:
        bnary.left, right = toLeft(bnary.left)
        return bnary, right

def delLeaf(bnary):
    bnary, right = toLeft(bnary)
    if bnary is None:
        bnary = binaryTree()
    return bnary if right is None else mkBntr(bnary, right)



if __name__ == '__main__':
    n, q = input().split()
    n, q = int(n), int(q)
    S = [binaryTree() for i in range(n)]
    for i in range(q):
        query = input().split()

        bnary = S[int(query[1])]
        if query[0] == '0':
            S[int(query[1])] = makeBntr(bnary, int(query[2]))

        else:
            if bnary.value is None:
                pass
            elif query[0] == '1':
                print(getLeaf(bnary))
            else:
                S[int(query[1])] = delLeaf(bnary)