// array with segment extraction in log n
#include <cstdlib>
#include <iostream>
using namespace std;

int random ()
{
	return (rand () << 15) ^ rand ();
}

struct Node;
typedef Node * PNode;
struct Node
{
	int value;
	int y;
	int size;
	PNode left;
	PNode right;

	Node (int value_)
	{
		value = value_;
		y = random ();
		size = 1;
		left = nullptr;
		right = nullptr;
	}

	void recalc ();
};

int getSize (PNode t)
{
	return (t == nullptr) ? 0 : t -> size;
}

void Node::recalc ()
{
	size = 1 + getSize (left) + getSize (right);
}

pair <PNode, PNode> tsplitK (PNode t, int k)
{
	if (t == nullptr) return {nullptr, nullptr};
	int leftSize = getSize (t -> left);
//	if (leftSize >= k)
	if (k - leftSize - 1 < 0)
	{
		auto temp = tsplitK (t -> left, k);
		// temp.first | {temp.second | t}
		t -> left = temp.second;
		t -> recalc ();
		return {temp.first, t};
	}
	else
	{
		auto temp = tsplitK (t -> right, k - leftSize - 1);
		t -> right = temp.first;
		t -> recalc ();
		return {t, temp.second};
	}
}

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);
		r -> recalc ();
		return r;
	}
	else
	{
		l -> right = tmerge (l -> right, r);
		l -> recalc ();
		return l;
	}
}

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

void toutput (PNode t)
{
	toutputrecur (t);
	cout << endl;
}

int main ()
{
	int n = 20;
	PNode root = nullptr;
	for (int i = 0; i < n; i++)
	{
		root = tmerge (root, new Node ((i * 3) % n));
		toutput (root);
	}

	{
		auto temp = tsplitK (root, 6);
		toutput (temp.first);
		toutput (temp.second);
		root = tmerge (temp.first, temp.second);
		toutput (root);
	}

	{
		auto temp = tsplitK (root, 6);
		auto right = tsplitK (temp.second, 1);
		cout << right.first -> value << endl;
		temp.second = tmerge (right.first, right.second);
		root = tmerge (temp.first, temp.second);
	}

	{
		int lo = 6;
		int me = 9;
		int hi = 16;
		//       temp.first                 temp.second
		// one.first   one.second     two.first     two.second
		// [0..lo)       [lo..me)      [me..hi)       [hi..n)
		// [0..lo)       [me..hi)      [lo..me)       [hi..n)
		auto temp = tsplitK (root, me);
		auto one = tsplitK (temp.first, lo);
		auto two = tsplitK (temp.second, hi - me);
		toutput (one.first);
		toutput (one.second);
		toutput (two.first);
		toutput (two.second);
		auto glue1 = tmerge (one.first, two.first);
		auto glue2 = tmerge (one.second, two.second);
		root = tmerge (glue1, glue2);
		toutput (root);
	}

	return 0;
}