#include <cstdlib>
#include <cstdio>

unsigned R() { return (rand() << 15) + rand(); }

struct tree;
typedef tree * ptree;

struct tree
{
  ptree l, r;
  int x, size;

  tree( int x, ptree l = 0, ptree r = 0 )
  {
    this->x = x, this->l = l, this->r = r;
    size = 1 + Sz(l) + Sz(r);
  }
  friend int Sz( ptree t );
};

inline int Sz( ptree t ) { return t ? t->size : 0; }

void Split( ptree t, ptree &l, ptree &r, int k ) // size(l) = k
{
  ptree tmp;
  if (!t)
    l = r = 0;
  else if (Sz(t->l) + 1 <= k)
  {
    Split(t->r, tmp, r, k - (Sz(t->l) + 1));
    l = new tree(t->x, t->l, tmp);
  }
  else
  {
    Split(t->l, l, tmp, k);
    r = new tree(t->x, tmp, t->r);
  }
}

ptree Merge( ptree l, ptree r )
{
  if (!l)
    return r;
  else if (!r)
    return l;
  else if ((int)(R() % (Sz(l) + Sz(r))) < Sz(l))
    return new tree(l->x, l->l, Merge(l->r, r));
  else
    return new tree(r->x, Merge(l, r->l), r->r);
}

void Out( ptree t )
{
  if (t)
    printf("("), Out(t->l), printf("%d", t->x), Out(t->r), printf(")");
}