#include <optional>
#include <format>

#pragma once

namespace cartesian {

template<class Key, class Priority>
struct Node;

template<class Key, class Priority>
struct Tree {
	using NodeKP = Node<Key, Priority>;
	NodeKP* root = nullptr;

	bool empty() const {
		return root == nullptr;
	}

	std::pair<Tree, Tree> split(Key xs, bool strict);

	static Tree merge(Tree l, Tree r);

	bool insert(Key x, Priority y);

	std::optional<Priority> erase(Key x);

	size_t clear();

	std::optional<Priority> find(Key x);

	std::string to_string() const;
	std::pair<std::string, std::vector<int>> to_leveled_string() const;
};

template<class Key, class Priority>
struct Node {
	using TreeKP = Tree<Key, Priority>;
	Key x;
	Priority y;
	TreeKP l, r;
};

template<class Key, class Priority>
auto Tree<Key, Priority>::split(Key xs, bool strict)
		-> std::pair<Tree, Tree> {
	if (empty())
		return {};
	bool root_is_left = strict ? root->x < xs : root->x <= xs;
	if (root_is_left) {
		auto [rl, rr] = root->r.split(xs, strict);
		root->r = rl;
		return { *this, rr };
	} else {
		auto [ll, lr] = root->l.split(xs, strict);
		root->l = lr;
		return { ll, *this };
	}
}

template<class Key, class Priority>
auto Tree<Key, Priority>::merge(Tree l, Tree r) -> Tree {
	if (l.empty())
		return r;
	if (r.empty())
		return l;
	bool root_is_left = r.root->y < l.root->y;
	if (root_is_left) {
		l.root->r = merge(l.root->r, r);
		return l;
	} else {
		r.root->l = merge(l, r.root->l);
		return r;
	}
}

template<class Key, class Priority>
bool Tree<Key, Priority>::insert(Key x, Priority y) {
	auto [l, r] = split(x, true);
	auto [rl, rr] = r.split(x, false);
	bool inserted = rl.empty();
	if (inserted)
		rl.root = new NodeKP{
			.x = x,
			.y = y,
			.l = {},
			.r = {},
		};
	r = merge(rl, rr);
	*this = merge(l, r);
	return inserted;
}

template<class Key, class Priority>
size_t Tree<Key, Priority>::clear() {
	if (empty())
		return 0;
	size_t ans = 0;
	ans += root->l.clear();
	ans += root->r.clear();
	delete root; ++ans;
	return ans;
}

template<class Key, class Priority>
std::optional<Priority> Tree<Key, Priority>::erase(Key x) {
	auto [l, r] = split(x, true);
	auto [rl, rr] = r.split(x, false);
	std::optional<Priority> ans;
	if (!rl.empty())
		ans = rl.root->y;
	rl.clear();
	*this = merge(l, rr);
	return ans;
}

template<class Key, class Priority>
std::optional<Priority> Tree<Key, Priority>::find(Key x) {
	auto [l, r] = split(x, true);
	auto [rl, rr] = r.split(x, false);
	std::optional<Priority> ans;
	if (!rl.empty())
		ans = rl.root->y;
	r = merge(rl, rr);
	*this = merge(l, r);
	return ans;
}

template<class Key, class Priority>
std::string Tree<Key, Priority>::to_string() const {
	if (empty())
		return "[]";
	std::string ans = "[";
	ans += root->l.to_string();
	ans += std::format("{{{} {}}}", root->x, root->y);
	ans += root->r.to_string();
	ans += ']';
	return ans;
}

template<class Key, class Priority>
std::pair<std::string, std::vector<int>>
Tree<Key, Priority>::to_leveled_string() const {
	if (empty())
		return { "[]", {0, 0} };
	std::string ans = "[";
	std::vector<int> lvl = { 0 };
	auto [lans, llvl] = root->l.to_leveled_string();
	ans += lans;
	for (int i : llvl)
		lvl.push_back(1 + i);
	std::string root_str = std::format("{{{} {}}}", root->x, root->y);
	ans += root_str;
	for (char c : root_str)
		lvl.push_back(0);
	auto [rans, rlvl] = root->r.to_leveled_string();
	ans += rans;
	for (int i : rlvl)
		lvl.push_back(1 + i);
	ans += ']';
	lvl.push_back(0);
	return { ans, lvl };
}

template<class Key>
struct Set {
	Tree<Key, int> tree;
	std::mt19937 rng;
	const int MIN_Y = -1'000'000'000;
	const int MAX_Y =  1'000'000'000;
	using uid = std::uniform_int_distribution<int>;

	void insert(Key x) {
		tree.insert(x, uid(MIN_Y, MAX_Y)(rng));
	}

	bool erase(Key x) {
		return tree.erase(x).has_value();
	}

	bool contains(Key x) {
		return tree.find(x).has_value();
	}

	~Set() {
		tree.clear();
	}
};
}