#define _GLIBCXX_DEBUG                                              
#include <bits/stdc++.h>
using namespace std;
 
mt19937 rng(450);

using ll = long long;
 
struct node
{
	int l, r;
	int x, y;

	int cnt;

	ll sum;
	int val;

	/// можно добавить какую-нибудь информацию в каждую вершину
	node() : l(-1), r(-1), x(-1), y(-1), cnt(-1), sum(0), val(0) {} ///val(-1) {}
 
	node(const int x_, const int val_) : l(-1), r(-1), x(x_), y(rng()), cnt(1), sum(val_), val(val_) {} ///val(val_) {}
};
 
struct treap_manager
{
	vector<node> v;
 
	pair<int, int> split (const int t, const int x0)
	{
		if (t == -1)
			return pair<int, int>(-1, -1);
 
		if (v[t].x >= x0)
		{
			///int l, r;
			///pair<int, int> p = split(v[t].l, x0);
			///l = p.first; r = p.second;
			auto [l, r] = split(v[t].l, x0);
			v[t].l = r;
			recalc(t);
			return pair<int, int>(l, t);
		}
		else
		{
			auto [l, r] = split(v[t].r, x0);
			v[t].r = l;
			recalc(t);
			return pair<int, int>(t, r);
		}
	}

	pair<int, int> split_by_size (const int t, const int k)
	{
		if (t == -1)
			return pair<int, int>(-1, -1);
 
		if (cnt(v[t].l) >= k)
		{
			///int l, r;
			///pair<int, int> p = split(v[t].l, x0);
			///l = p.first; r = p.second;
			auto [l, r] = split_by_size(v[t].l, k);
			v[t].l = r;
			recalc(t);
			return pair<int, int>(l, t);
		}
		else
		{
			auto [l, r] = split_by_size(v[t].r, k - cnt(v[t].l) - 1);
			v[t].r = l;
			recalc(t);
			return pair<int, int>(t, r);
		}
	}

	ll sum (const int t)
	{
		return t == -1 ? 0LL : v[t].sum;
	}

	void recalc (const int t)
	{
		if (t != -1)
		{
			v[t].cnt = cnt(v[t].l) + 1 + cnt(v[t].r);
			v[t].sum = sum(v[t].l) + v[t].val + sum(v[t].r);
		}
	}
 
	int merge (const int l, const int r)
	{
		if (l == -1)
			return r;
		if (r == -1)
			return l;
 
		if (v[l].y > v[r].y)
		{
			v[l].r = merge(v[l].r, r);
			recalc(l);
			return l;
		}
		else
		{
			v[r].l = merge(l, v[r].l);
			recalc(r);
			return r;
		}
	}

	int cnt (const int t)
	{
		return t == -1 ? 0 : v[t].cnt;
	}
 
	int newnode (const int x, const int val)
	{
		v.push_back(node(x, val));
		return int(v.size()) - 1;
	}
 
	void print_with_newline (int &t)
	{
		print_order(t);
		cout << endl;
	
		for (int i = 0; i < cnt(t); i++)
			cout << get_kth_stat(t, i) << " ";
		cout << endl;
                   

		for (int i = 0; i < cnt(t); i++)	
			cout << get_kth_stupid(t, i) << " ";
		cout << endl;
		cout << "======" << endl;
	}
 
 
	void print_order (const int t)
	{
		if (t == -1)
			return;
 
		print_order(v[t].l);
		cout << v[t].x << " ";
		print_order(v[t].r);
	}
 
	void insert (int &root, const int x, const int val)
	{
		const int m = newnode(x, val);
		auto [l, r] = split(root, x);
	 	root = merge(merge(l, m), r);
	}
 
	void erase (int &root, const int x)
	{
		auto [l, temp] = split(root, x);
		auto [m, r] = split(temp, x + 1);
		root = merge(l, r);
	}

	int get_kth_stat (const int root, const int k)
	{
		assert(root != -1);
		assert(0 <= k && k < cnt(root));
		const int pivot = cnt(v[root].l);

		if (k < pivot)
			return get_kth_stat(v[root].l, k);
		else if (k == pivot)
			return v[root].x;
		else
			return get_kth_stat(v[root].r, k - pivot - 1);	
	}

	int get_kth_stupid (int &root, const int k)
	{
		auto [l, temp] = split_by_size(root, k);
		auto [m, r] = split_by_size(temp, 1);
		assert(m != -1);
		const int ans = v[m].x;
		root = merge(merge(l, m), r);
		return ans;
	}

	/// [xl, xr)
	ll get_sum (int &root, const int xl, const int xr)
	{
		auto [l, temp] = split(root, xl);
		auto [m, r] = split(temp, xr);
		const ll ans = sum(m);
		root = merge(merge(l, m), r);
		return ans;
	}	
};
 
int main()
{
	treap_manager info;
 
	int root = -1;
	info.insert(root, 3, 11);
	info.print_with_newline(root);	
	info.insert(root, -1, 7);
	cout << "query: " << info.get_sum(root, -1, 3) << " " << info.get_sum(root, -1, 4) << endl;
	cout << "query: " << info.get_sum(root, 0, 3) << " " << info.get_sum(root, 0, 4) << endl;
	info.print_with_newline(root);
	info.insert(root, 4, -2);
	info.print_with_newline(root);
	info.insert(root, 2, 100);
	info.print_with_newline(root);
	cout << "query: " << info.get_sum(root, -100, 100) << endl;
	info.erase(root, 2);
	cout << "query: " << info.get_sum(root, -100, 100) << endl;
	info.print_with_newline(root);
	info.erase(root, 2);
	cout << "query: " << info.get_sum(root, -100, 100) << endl;
}