#include <fstream>
#include <cstdlib>

using namespace std;

typedef struct NODE
{
	int key, pri;
	NODE *left, *right;
	NODE(int k) : key(k), pri(rand() * rand()), left(NULL), right(NULL)
	{
		;
	}
	~NODE(void)
	{
		delete left;
		delete right;
	}
} *PNODE;

PNODE root = NULL;

void rotate_left(PNODE &t)
{
	PNODE q = t->right;
	t->right = q->left;
	q->left = t;
	t = q;
}

void rotate_right(PNODE &t)
{
	PNODE q = t->left;
	t->left = q->right;
	q->right = t;
	t = q;
}

void insert(PNODE &p, int key)
{
	if(p == NULL)
	{
		p = new NODE(key);
		return;
	}
	if(key < p->key)
	{
		insert(p->left, key);
		if(p->left->pri < p->pri)
		{
			rotate_right(p);
		}
	}
	else
	{
		insert(p->right, key);
		if(p->right->pri < p->pri)
		{
			rotate_left(p);
		}
	}
}

ofstream fout("output.txt");

void traverse(PNODE p)
{
	if(p->left != NULL)
	{
		traverse(p->left);
	}
	fout << p->key << "\n";
	if(p->right != NULL)
	{
		traverse(p->right);
	}
}

int main(void)
{
	ifstream fin("data.txt");
	int key;
	while(fin >> key)
	{
		insert(root, key);
	}
	traverse(root);
	delete root;
	fout.close();
	return 0;
}