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.

Constraints

* $1 \leq n \leq 1,000$
* $1 \leq q \leq 200,000$
* $-1,000,000,000 \leq x \leq 1,000,000,000$

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.

Example

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


Output

9
3
4
8

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
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')
	elif A[query[2:-1]]:
		heappop(A[query[2:-1]])
sys.stdout.writelines(ans)


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()


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


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])
	elif box[b]:
		heappop(box[b])


class MaxHeapInt(object):

	def __init__(self, val):
		self.val = val

	def __lt__(self, other):
		return self.val > other.val

	def __eq__(self, other):
		return self.val == other.val

	def __str__(self):
		return str(self.val)

def resolve():
	import heapq
	(n, Q) = [int(i) for i in input().split()]
	ans = [[] for _ in range(n)]
	for _ in range(Q):
		q = [int(i) for i in input().split()]
		if q[0] == 0:
			heapq.heappush(ans[q[1]], MaxHeapInt(q[2]))
		elif q[0] == 1:
			if len(ans[q[1]]) > 0:
				print(ans[q[1]][0].val)
		elif len(ans[q[1]]) > 0:
			heapq.heappop(ans[q[1]])
resolve()


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()


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


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])
	elif len(Q[query[1]]) > 0:
		Q[query[1]].pop(-1)


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':
		x = int(list_num[1])
		bisect.insort(Q[t], x)
	elif command == '1':
		if Q[t]:
			print(Q[t][-1])
	elif command == '2':
		if Q[t]:
			del Q[t][-1]
	else:
		raise


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 = []
for query in queries:
	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])


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]])


from heapq import heappush, heappop
(n, q) = list(map(int, input().split(' ')))
pqueues = [[] for i in range(n)]
for i in range(q):
	op = list(map(int, input().split(' ')))
	if op[0] == 0:
		heappush(pqueues[op[1]], -op[2])
	elif op[0] == 1:
		if len(pqueues[op[1]]) != 0:
			print(-1 * pqueues[op[1]][0])
	elif op[0] == 2:
		if len(pqueues[op[1]]) != 0:
			heappop(pqueues[op[1]])


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


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)


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]])


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]])


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)
	elif pq[int(t)]:
		heappop(pq[int(t)])


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)


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)
loop_proc()


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]])


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]])


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])
	elif a[c[1]]:
		heapq.heappop(a[c[1]])


import heapq

def insert(t, x):
	global Qlist
	heapq.heappush(Qlist[t], -x)

def getMax(t):
	global Qlist
	if Qlist[t]:
		num = Qlist[t][0]
		print(-num)

def deleteMax(t):
	global Qlist
	if Qlist[t]:
		heapq.heappop(Qlist[t])
Qlist = []
(n, q) = map(int, input().split())
for i in range(n):
	Qi = []
	heapq.heapify(Qi)
	Qlist.append(Qi)
for i in range(q):
	queryi = list(map(int, input().split()))
	if queryi[0] == 0:
		insert(queryi[1], queryi[2])
	elif queryi[0] == 1:
		getMax(queryi[1])
	else:
		deleteMax(queryi[1])


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)


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':
		heapq.heappush(queues[arg[0]], -int(arg[1]))
	elif query == '1':
		if len(queues[arg[0]]):
			print(-queues[arg[0]][0])
	elif query == '2':
		if len(queues[arg[0]]):
			heapq.heappop(queues[arg[0]])
	else:
		raise AssertionError


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


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


from sys import stdin
import heapq
(n, q) = map(int, input().split())
q_list = [list() for i in range(n)]
for i in range(q):
	l = list(map(int, stdin.readline().split()))
	if l[0] == 0:
		heapq.heappush(q_list[l[1]], -l[2])
	elif l[0] == 1:
		if q_list[l[1]]:
			print(-q_list[l[1]][0])
	elif q_list[l[1]]:
		heapq.heappop(q_list[l[1]])


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])
	elif H[q[1]]:
		heapq.heappop(H[q[1]])


import heapq
(n, q) = map(int, input().split())
S = [[] for i in range(n)]
for i in range(q):
	query = tuple(map(int, input().split()))
	if query[0] == 0:
		heapq.heappush(S[query[1]], -1 * query[2])
	elif query[0] == 1:
		if len(S[query[1]]) != 0:
			a = heapq.heappop(S[query[1]])
			print(-1 * a)
			heapq.heappush(S[query[1]], a)
	elif len(S[query[1]]) != 0:
		heapq.heappop(S[query[1]])


from __future__ import print_function
import sys
import heapq
(n, q) = map(int, sys.stdin.readline().split())
a = [[] for i in range(n)]
for i 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]])


class MaxPQ:

	def __init__(self):
		self.q = []

	def insert(self, x):
		self.q.append(x)
		self.swim(len(self.q) - 1)

	def get_max(self):
		if len(self.q) > 0:
			return self.q[0]
		else:
			return None

	def delete_max(self):
		if len(self.q) == 0:
			return
		val = self.q.pop()
		if len(self.q) > 0:
			self.q[0] = val
			self.sink(0)

	def sink(self, i):
		c1 = (i + 1) * 2 - 1
		c2 = (i + 1) * 2
		size = len(self.q)
		if c1 >= size:
			pass
		elif c1 < size and c2 >= size:
			if self.q[c1] > self.q[i]:
				(self.q[c1], self.q[i]) = (self.q[i], self.q[c1])
				self.sink(c1)
		elif self.q[c1] > self.q[c2]:
			if self.q[c1] > self.q[i]:
				(self.q[c1], self.q[i]) = (self.q[i], self.q[c1])
				self.sink(c1)
		elif self.q[c2] > self.q[i]:
			(self.q[c2], self.q[i]) = (self.q[i], self.q[c2])
			self.sink(c2)

	def swim(self, i):
		p = (i + 1) // 2 - 1
		if p >= 0:
			if self.q[p] < self.q[i]:
				(self.q[p], self.q[i]) = (self.q[i], self.q[p])
				self.swim(p)

def run():
	(n, q) = [int(x) for x in input().split()]
	pqs = [MaxPQ() for _ in range(n)]
	for _ in range(q):
		com = [int(x) for x in input().split()]
		c = com[0]
		if c == 0:
			(t, v) = com[1:]
			pqs[t].insert(v)
		elif c == 1:
			t = com[1]
			val = pqs[t].get_max()
			if val is not None:
				print(val)
		elif c == 2:
			t = com[1]
			pqs[t].delete_max()
		else:
			raise ValueError('invalid command')
run()


from heapq import heapify, heappop, heappush
(heap_num, query_num) = map(lambda x: int(x), input().split())
heaps = [[] for _ in range(heap_num)]
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


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])
		elif len(Q[query[1]]) != 0:
			heapq.heappop(Q[query[1]])
main()


import heapq as hq
(n, q) = map(int, input().split())
queues = [[] for i in range(n)]
while q:
	q -= 1
	s = [*map(int, input().split())]
	if s[0] == 0:
		hq.heappush(queues[s[1]], -s[2])
	elif s[0] == 1 and queues[s[1]]:
		print(-queues[s[1]][0])
	elif queues[s[1]]:
		hq.heappop(queues[s[1]])


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


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])


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])


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])


import heapq

def main():
	(n, m) = map(int, input().split())
	pq = [[] for _ in range(n)]
	for i in range(n):
		heapq.heapify(pq[i])
	for _ in range(m):
		q = input().split()
		if q[0] == '0':
			heapq.heappush(pq[int(q[1])], -int(q[2]))
		elif pq[int(q[1])]:
			if q[0] == '1':
				print(-pq[int(q[1])][0])
			else:
				heapq.heappop(pq[int(q[1])])
main()


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])


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


import heapq
(n, q) = map(int, input().split())
A = [[] for i in range(n)]
for i in range(q):
	tmp = list(map(int, input().split()))
	if tmp[0] == 0:
		heapq.heappush(A[tmp[1]], -tmp[2])
	elif tmp[0] == 1 and A[tmp[1]]:
		print(-A[tmp[1]][0])
	elif tmp[0] == 2 and A[tmp[1]]:
		heapq.heappop(A[tmp[1]])