#include <bits/stdc++.h>
#include <random>

using X = int;
using Y = int;

int genRandInt(int from, int to)
{
    static std::mt19937_64 gen;

    std::uniform_int_distribution distribution(from, to);

    return distribution(gen);
}

struct Node
{
    X x;
    Y y;
    size_t index;
    Node* siblings[2];
};

void print(const Node& node);
const Node* find(const Node& node, X x);

class Treap final
{
public:
    explicit Treap();

    void insert(X x);
    void erase(X x);
    bool contains(X x) const;

    std::pair<Treap, Treap> split(X x) &&;
    void merge(Treap&& other);

    void print() const;

private:
    Node* findByX(X x) const;

    Node* root;
};

const Node* find(const Node& node, X x)
{
    if (node.x == x)
    {
        return &node;
    }

    if (node.x < x)
    {
        if (node.siblings[1])
        {
            return find(*node.siblings[1], x);
        }
        else
        {
            return nullptr;
        }
    }
    else
    {
        if (node.siblings[0])
        {
            return find(*node.siblings[0], x);
        }
        else
        {
            return nullptr;
        }
    }
}

void print(const Node& node)
{
    if (node.siblings[0] != nullptr)
    {
        print(*node.siblings[0]);
    }

    std::cout << "x: " << node.x << "; y: " << node.y << "; index: " << node.index << std::endl;

    if (node.siblings[1] != nullptr)
    {
        print(*node.siblings[1]);
    }
}

Treap::Treap() = default;

void Treap::print() const
{
    std::cout << "Treap" << std::endl;

    assert(root);
    ::print(*root);

    std::cout << std::endl;
}

bool Treap::contains(X x) const
{
    assert(root);
    return nullptr != find(*root, x);
}

void Treap::insert(X x)
{
    assert(not contains(x));

    auto [left, right] = std::move(*this).split(x);

    Node node
    {
          .x = x
        , .y = genRandInt(0, 100)
        , .index = 0
        , .siblings = {nullptr, nullptr}
    };

    root = new Node(node);

    left.merge(std::move(*this));
    left.merge(std::move(right));

    root = left.root;

//    root = new Node
//    (
//          x
//        , genRandInt(0, 100)
//        , 0
//        , {nullptr, nullptr}
//    );
}

int main(const int argc, const char** argv)
{
    Treap t;

    for (int i = 0; i < 10; ++i)
    {
        t.insert(genRandInt(0, 100));
    }

    t.print();

//    auto [left, right] = std::move(t).split(50);
//
//    left.print();
//    right.print();
}