Problem: 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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

template<class Ty>
class priority {
	vector<Ty> inst;
public:
	bool empty() const { return inst.empty(); }
	size_t size() const { return inst.size(); }
	void shrink_to_fit() { inst.shrink_to_fit(); }
	void reserve(size_t s) { inst.reserve(s); }
	void insert(const Ty & a) {
		size_t i = size();
		inst.push_back(a);
		while (inst(i) < inst((i - 1) / 2)) {
			swap(inst[i], inst[(i - 1) / 2]);
			i = (i - 1) / 2;
		}
	}
	void insert(Ty && a) {
		size_t i = size();
		inst.push_back(a);
		while (i != 0) {
			if (inst[i] >= inst[(i - 1) / 2]) break;
			swap(inst[i], inst[(i - 1) / 2]);
			i = (i - 1) / 2;
		}
	}
	const Ty &get() {
		return inst.front();
	}
	void pop() {
		swap(inst.front(), inst.back());
		inst.pop_back();
		size_t i = 0;
		while (true) {
			if (size() <= i * 2 + 1) break;
			if (size() > i * 2 + 2) {
				int j = (inst[i * 2 + 1] < inst[i * 2 + 2]) ? (i * 2 + 1) : (i * 2 + 2);
				if (inst[j] < inst[i]) {
					swap(inst[j], inst[i]);
					i = j;
					continue;
				}
			}
			else if (size() > i * 2 + 1) {
				if (inst[i * 2 + 1] < inst[i]) {
					swap(inst[i * 2 + 1], inst[i]);
					i = i * 2 + 1;
					continue;
				}
			}
			break;
		}
	}
	Ty pick() {
		Ty buf = move(inst.front());
		pop();
		return move(buf);
	}
};

int main(){
	int n, q; cin >> n >> q;
	vector<priority<int>> Q(n);
	vector<int> ans;

	for (int i = 0; i < q; i++) {
		int c; cin >> c;
		if (c == 0) {
			int t, v; cin >> t >> v;
			Q[t].insert(-v);
		}
		if (c == 1) {
			int t; cin >> t;
			if(!Q[t].empty()) ans.push_back(- Q[t].get());
		}
		if (c == 2) {
			int t; cin >> t;
			if (!Q[t].empty()) Q[t].pop();
		}
	}
	for (int i : ans) cout << i << endl;

	return 0;
}