// 1. Split and merge. Insert and output.
#include <bits/stdc++.h>
using namespace std;

using Num = int;

#ifdef DEBUG
int const limit = 10;
#else
int const limit = 1000000;
#endif

mt19937 gen (1251521589);
uniform_int_distribution <int> rnd (0, 1000000000);

struct Node;
typedef Node * PNode;
struct Node
{
	Num x;
	int y;
	PNode left;
	PNode right;

	Node (Num x_)
	{
		x = x_;
		y = rnd (gen);
		left = nullptr;
		right = nullptr;
	}
};

pair <PNode, PNode> tSplit (PNode t, Num x)
{
	if (t == nullptr) return {nullptr, nullptr};
	if (t -> x < x)
	{
		auto temp = tSplit (t -> right, x);
		t -> right = temp.first;
		return {t, temp.second};
	}
	else
	{
		auto temp = tSplit (t -> left, x);
		t -> left = temp.second;
		return {temp.first, t};
	}
}

PNode tMerge (PNode l, PNode r)
{
	if (l == nullptr) return r;
	if (r == nullptr) return l;
	if (l -> y < r -> y)
	{
		r -> left = tMerge (l, r -> left);
		return r;
	}
	else
	{
		l -> right = tMerge (l -> right, r);
		return l;
	}
}

PNode tInsert (PNode t, Num x)
{
	auto temp = tSplit (t, x);
	auto v = new Node (x);
	auto half = tMerge (temp.first, v);
	return tMerge (half, temp.second);
}

void tOutputRecur (PNode t)
{
	if (t == nullptr) return;
	cout << "(";
	tOutputRecur (t -> left);
	cout << t -> x;
	tOutputRecur (t -> right);
	cout << ")";
}

void tOutput (PNode t)
{
#ifdef DEBUG
	cout << t -> x << " ";
	tOutputRecur (t);
	cout << endl;
#endif
}

int main ()
{
	PNode root = nullptr;
	cout << "limit = " << limit << endl;
	for (int i = 0; i < limit; i++)
	{
		root = tInsert (root, (i * 3) % limit);
		tOutput (root);
	}
	return 0;
}