/// Treap (Cartesian Tree)
///   Store x (key) and y (priority)
///   Store value
///   Maintain size of subtree
///   total: sum of values in subtree
/// Base Functions
///   tSplit: split into <x and >=x
///   tMerge: merge trees l and r if {keys of l} <= {keys of r}
/// Map Interface (Multimap)
///   tInsert: add (x, value) pair into map
///   tFind: return value for given key x
///   tAssign: assign value for given key x, assume at least one exists
///   tRemove: erase all keys x from map
/// Debugging
///   tOutput: print bracket structure of tree
/// Example Usage
///   Add 10^7 elements
///   Find 10^7 elements
///   Split into two parts, check sizes
///   Cut middle part, check total
///   Reassign an element in the middle
///   Cut middle part, check total again
///   Remove 10^7 elements
#include <bits/stdc++.h>
using namespace std;

auto gen = mt19937 (time (0));
auto uniform = uniform_int_distribution <int> (0, int (1E9));

struct Node;
using PNode = Node *;
int getSize (PNode t);
using Num = long long;
Num getTotal (PNode t);
struct Node
{
	int x;
	Num value;
	Num total;
	int y;
	int size;
	PNode left;
	PNode right;
	
	void recalc ()
	{
		size = 1 + getSize (left) + getSize (right);
		total = value + getTotal (left) + getTotal (right);
	}

	Node (int x_, Num value_)
	{
		x = x_;
		value = value_;
		total = value_;
		y = uniform (gen);
		size = 1;
		left = nullptr;
		right = nullptr;
	}

	~Node ()
	{
		if (left != nullptr) delete left;
		if (right != nullptr) delete right;
	}
};

int getSize (PNode t)
{
	return t == nullptr ? 0 : t -> size;
}

Num getTotal (PNode t)
{
	return t == nullptr ? Num (0) : t -> total;
}

pair <PNode, PNode> tSplit (PNode t, int x)
{
	if (t == nullptr) return {nullptr, nullptr};
	if (t -> x >= x)
	{
		auto p = tSplit (t -> left, x);
		t -> left = p.second;
		t -> recalc ();
		return {p.first, t};
	}
	else
	{
		auto p = tSplit (t -> right, x);
		t -> right = p.first;
		t -> recalc ();
		return {t, p.second};
	}
}

PNode tMerge (PNode l, PNode r)
{
	if (l == nullptr) return r;
	if (r == nullptr) return l;
	if (l -> y < r -> y)
	{
		r -> left = tMerge (l, r -> left);
		r -> recalc ();
		return r;
	}
	else
	{
		l -> right = tMerge (l -> right, r);
		l -> recalc ();
		return l;
	}
}

PNode tInsert (PNode t, int x, Num value)
{
	auto v = new Node (x, value);
	auto p = tSplit (t, x);
	auto half = tMerge (p.first, v);
	return tMerge (half, p.second);
}

void tOutput (PNode t, bool doEndl = true)
{
	if (t != nullptr)
	{
		cout << '(';
		tOutput (t -> left, false);
		cout << t -> x << ':' << t -> value <<
		    '|' << t -> size << '"' << t -> total;
		tOutput (t -> right, false);
		cout << ')';
	}
	if (doEndl) cout << '.' << endl;
}

Num tFind (PNode t, int x)
{
	if (t == nullptr) return Num (-1);
	if (t -> x == x) return t -> value;
	if (t -> x < x) return tFind (t -> right, x);
	else return tFind (t -> left, x);
}

PNode tAssign (PNode t, int x, Num value)
{
	auto p = tSplit (t, x);
	auto q = tSplit (p.second, x + 1);
	q.first -> value = value;
	q.first -> recalc ();
	p.second = tMerge (q.first, q.second);
	return tMerge (p.first, p.second);
}

PNode tRemove (PNode t, int x)
{
	auto p = tSplit (t, x);
	auto q = tSplit (p.second, x + 1);
	delete q.first;
	return tMerge (p.first, q.second);
}

int main ()
{
/*
	Node u;
	u.left; u.right;
	PNode v;
	(*v).left; (*v).right;
	v -> left; v -> right;
*/
	int const limit = int (1E7);
	PNode root = nullptr;
	
	for (int x = 1; x <= limit; x++)
	{
		root = tInsert (root, x * 2, (x * 1LL * x) % 17);
		if (x <= 10) tOutput (root);
	}
	
	for (int x = 1; x <= limit; x++)
	{
		auto res = tFind (root, x);
		if (x <= 10) cout << x << ' ' << res << endl;
	}
	
	{
		auto p = tSplit (root, limit * 2 - 5);
		cout << "sizes: " << getSize (p.first) << " " <<
		    getSize (p.second) << endl;
		root = tMerge (p.first, p.second);
	}

	{
		auto p = tSplit (root, 3333333);
		auto q = tSplit (p.second, 6666666);
		cout << "total: " << getTotal (q.first) << endl;
		p.second = tMerge (q.first, q.second);
		root = tMerge (p.first, p.second);
	}

	{
		root = tAssign (root, 5000000, 10000);
	}

	{
		auto p = tSplit (root, 3333333);
		auto q = tSplit (p.second, 6666666);
		cout << "total: " << getTotal (q.first) << endl;
		p.second = tMerge (q.first, q.second);
		root = tMerge (p.first, p.second);
	}

	for (int x = 1; x <= limit; x++)
	{
		root = tRemove (root, x * 2);
		if (limit - x <= 10) tOutput (root);
	}
	
	return 0;
}