// treap as array
#include <bits/stdc++.h>
using namespace std;

mt19937 gen (123);
typedef uniform_int_distribution <int> uniform;

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

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

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

pair <PNode, PNode> tSplitK (PNode t, int k)
{ //  .first = left k,  .second = right n-k
	if (t == nullptr)
	{
		return {nullptr, nullptr};
	}
	int leftSize = (t -> left == nullptr) ? 0 : t -> left -> size;
	if (leftSize + 1 <= k)
	{
		auto temp = tSplitK (t -> right, k - leftSize - 1);
		t -> right = temp.first;
		t -> recalc ();
		return {t, temp.second};
	}
	else
	{
		auto temp = tSplitK (t -> left, k);
		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 (uniform (0, l -> size + r -> size - 1) (gen) < l -> size)
	{
		l -> right = tMerge (l -> right, r);
		l -> recalc ();
		return l;
	}
	else
	{
		r -> left = tMerge (l, r -> left);
		r -> recalc ();
		return r;
	}
}

PNode tInsertPos (PNode t, int pos, int value)
{
	auto temp = tSplitK (t, pos);
	auto v = new Node (value); // temp.first | v | temp.second
	auto half = tMerge (temp.first, v);
	return tMerge (half, temp.second);
}

int tKth (PNode & t, int k)
{
	auto temp = tSplitK (t, k);
	auto half = tSplitK (temp.second, 1);
	int res = half.first -> value;
	temp.second = tMerge (half.first, half.second);
	t = tMerge (temp.first, temp.second);
	return res;
}

PNode tToBack (PNode & t, int k, int r)
{  // [0..k) [k..r) [r..$) -> [0..k) [r..$) [k..r)
   // one   |                             
   // one.1 |    two                      
   //                                   three
   // one.1  concatenate with  three
	auto one = tSplitK (t, k);
	auto two = tSplitK (one.second, r - k);
	auto three = tMerge (two.second, two.first);
	return tMerge (one.first, three);
}

void tOutput (PNode t)
{
	if (t != nullptr)
	{
		cout << "(";
		tOutput (t -> left);
		cout << t -> value << "|" << t -> size;
		tOutput (t -> right);
		cout << ")";
	}
}

int main ()
{
	PNode root = nullptr;
	while (true)
	{
		string cmd;
		int value, k, r;
		cin >> cmd;
		if (cmd == "insert")
		{
			cin >> k >> value;
			root = tInsertPos (root, k, value);
		}
		else if (cmd == "output")
		{
			tOutput (root);
			cout << "\n";
		}
		else if (cmd == "kth")
		{
			cin >> k;
			cout << tKth (root, k) << "\n";
		}
		else if (cmd == "toback")
		{
			cin >> k >> r;
			root = tToBack (root, k, r);
			cout << "\n";
		}
		else
		{
			break;
		}
	}
	return 0;
}