// kth order statistic
#include <cstdlib>
#include <iostream>
#include <utility>
using namespace std;

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

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

	Node (int x_)
	{
		x = x_;
		y = random ();
		size = 1;
		left = nullptr;
		right = nullptr;
	}

	void recalc ()
	{
//		size = 1 + left -> size + right -> size;
		size = 1;
		if (left != nullptr) size += left -> size;
		if (right != nullptr) size += right -> size;
	}
};

bool tfind (PNode t, int xf)
{
	if (t == nullptr) return false;
	if (t -> x == xf) return true;
	if (t -> x < xf) return tfind (t -> right, xf);
	else return tfind (t -> left, xf);
}

pair <PNode, PNode> tsplit (PNode t, int xs)
{
	if (t == nullptr) return {nullptr, nullptr};
	if (t -> x < xs)
	{
		auto temp = tsplit (t -> right, xs);
		// t -> left | t | temp.first | temp.second
		t -> right = temp.first;
		t -> recalc ();
		return {t, temp.second};
	}
	else
	{ // t -> x >= xs
		auto temp = tsplit (t -> left, xs);
		// temp.first | temp.second | t | t -> right
		t -> left = temp.second;
		t -> recalc ();
		return {temp.first, t};
	}
}

pair <PNode, PNode> tsplitK (PNode t, int k)
{
	if (t == nullptr) return {nullptr, nullptr};
	int leftSize = (t -> left == nullptr) ? 0 : t -> left -> size;
	if (k - leftSize - 1 >= 0) // where root will be?
//	if (k > leftSize)
	{
		auto temp = tsplitK (t -> right, k - leftSize - 1);
		// t -> left | t | temp.first | temp.second
		t -> right = temp.first;
		t -> recalc ();
		return {t, temp.second};
	}
	else
	{ // k <= leftSize
		auto temp = tsplitK (t -> left, k);
		// temp.first | temp.second | t | t -> right
		t -> left = temp.second;
		t -> recalc ();
		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);
		r -> recalc ();
		return r;
	}
	else
	{
		l -> right = tmerge (l -> right, r);
		l -> recalc ();
		return l;
	}
}

PNode tinsert (PNode t, int x)
{
	auto temp = tsplit (t, x);
	auto v = new Node (x);
	// temp.first | v | temp.second
	auto half = tmerge (temp.first, v);
	return tmerge (half, temp.second);
}

void tdelete (PNode t)
{
	if (t == nullptr) return;
	tdelete (t -> left);
	tdelete (t -> right);
	delete t;
}

PNode terase (PNode t, int x)
{
	auto temp = tsplit (t, x);
	auto half = tsplit (temp.second, x + 1);
	// temp.fitst < x  |  half.first == x  |  half.second > x
	tdelete (half.first);
	// delete half.first;
	return tmerge (temp.first, half.second);
}

int kth (PNode & root, int k)
{
	auto temp = tsplitK (root, k);
	auto half = tsplitK (temp.second, 1);
	// temp.first:k  half.first:1  half.second:n-k-1
	int res = half.first -> x;
	temp.second = tmerge (half.first, half.second);
	root = tmerge (temp.first, temp.second);
	return res;
}

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

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

int main ()
{
	int n = 10;
	PNode root = nullptr;
	for (int i = 0; i < n; i++)
	{
		root = tinsert (root, (i * 3 + 1) % n);
		toutput (root);
	}
	for (int i = 1; i < n; i++)
	{
		auto temp = tsplitK (root, i);
		toutputrecur (temp.first);
		cout << " | ";
		toutput (temp.second);
		root = tmerge (temp.first, temp.second);
	}
	for (int i = 0; i < n; i++)
	{
		cout << kth (root, (i * 7) % n) << " ";
	}
	cout << endl;
	return 0;
}