#include <bits/stdc++.h>
#define int long long
using namespace std;

struct node {
	int key, priority;
	node * left, * right;
	node (int nkey, int npriority){ key = nkey, priority = npriority , left = nullptr , right = nullptr;}
};

void split (node *& t, int key, node *& l, node *& r) {
	if (!t)
		l = r = nullptr;
	else if (key < t->key)
		split (t->left, key, l, t->left),  r = t;
	else
		split (t->right, key, t->right, r),  l = t;
}
void insert (node *&t, node *add) {
	if (t == nullptr)
		t = add;
	else if (add->priority > t->priority)
		split (t, add->key, add->left, add->right),  t = add;
	else
		insert (add->key < t->key ? t->left : t->right, add);
}

void print_tree(node *& tree) {
	if(tree == nullptr) {
		cout << "null" << endl;
		return;
	}
	cout << tree -> key << " " << tree -> priority << endl;
	print_tree(tree -> left);
	print_tree(tree -> right);
}
main() {
	int n;
	cin >> n;
	int x[n], y[n];
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	node *tree = nullptr;
	for(int i = 0; i < n; i++) {
		node *tmp = new node(x[i], y[i]);
		insert(tree, tmp);
	}
	print_tree(tree);
}