#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Treap {
    int x;  int y;  int sz;
    Treap* left;  Treap* right;

    Treap (int x_, int y_) :
        x(x_), y(y_), sz(1),
        left(nullptr), right(nullptr)
    { }
};

typedef Treap* Node;

int get_sz (Node t) {
    if (t == nullptr) {return 0;}
    return t->sz;
}

/* Size recalculation can not be done by just
subtracting / adding smth to the current size,
a separate function is needed. */
void sz_recalc (Node t) {
    if (t == nullptr) return;
    t->sz = get_sz (t->left)
            + get_sz (t->right) + 1;
}

Node treap_merge (Node t1, Node t2) {
    if (t1 == nullptr) return t2;
    if (t2 == nullptr) return t1;

    if (t1->y > t2->y) {
        t1->right = treap_merge (t1->right, t2);
        sz_recalc (t1);
        return t1;
    }

    t2->left = treap_merge (t1, t2->left);
    sz_recalc (t2);
    return t2;
}

pair <Node, Node> treap_split (Node t, int x0) {
    // It is guaranteed that all x's are different
    if (t == nullptr) return {nullptr, nullptr};

    if (x0 < t->x) {
        auto p = treap_split (t->left, x0);
        t->left = p.second;
        sz_recalc (t);
        return {p.first, t};
    }

    auto p = treap_split (t->right, x0);
    t->right = p.first;
    sz_recalc (t);
    return {t, p.second};
}

void treap_print (Node t) {
    if (t==nullptr) return;

    cout << "[";
    treap_print (t->left);
    cout << " (" << t->x << ", " << t->y
         << ", " << t->sz << ") ";
    treap_print (t->right);
    cout << "]";
}

Node treap_insert (Node t0, int x0, int y0) {
    auto p = treap_split (t0, x0);
    Node t = new Treap (x0, y0);
    return treap_merge(
        p.first,
        treap_merge (t, p.second)
    ); 
}

Node treap_find_k (Node t, int k) {
    if (t == nullptr) return nullptr;
    if (k == get_sz (t->left)) return t;
    if (k < get_sz (t->left)) return treap_find_k (t->left, k);
    return treap_find_k (t->right, k - get_sz (t->left) - 1);
}

pair <Node, Node> treap_split_k (Node t, int k) {
    if (t == nullptr) return {nullptr, nullptr};

    if (k <= get_sz(t->left)) {
        auto p = treap_split_k (t->left, k);
        t->left = p.second;
        sz_recalc (t);
        return {p.first, t};
    }

    auto p = treap_split_k (t->right, k - get_sz(t->left) - 1);
    t->right = p.first;
    sz_recalc (t);
    return {t, p.second};
}

int main ( ) {
    Node t0 = new Treap (14, 6);

    vector <pair <int, int>> v = {
        {6, 5}, {16, 4}, {8, 1}, {12, 3},
        {0, 2}, {10, 9}, {4, 8}, {18, 7}
    };

    for (auto p : v)
        t0 = treap_insert (t0, p.first, p.second);
    
    treap_print (t0);  cout << endl;

    auto p = treap_split_k (t0, 6);
    treap_print (p.first); cout << endl;
    treap_print(p.second);

    return 0;
}