#include "expr.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXP = 2e7 + 5;
const int MAXN = 2e4 + 5;
const int MAXK = 1e2 + 5;
struct Treap {
	struct Node {
		int lc, rc, type, size;
		Data res; bool rev;
	} a[MAXP];
	int size; Data t;
	unsigned seed = 1u << 30;
	unsigned rnd() {
		seed = seed * seed + rand();
		return seed;
	}
	int pushdown(int root) {
		if (a[root].rev) {
			int ans = ++size;
			a[ans] = a[root];
			a[ans].rev = false;
			a[++size] = a[a[root].lc];
			a[size].rev ^= true;
			a[++size] = a[a[root].rc];
			a[size].rev ^= true;
			a[ans].lc = size;
			a[ans].rc = size - 1;
			return ans;
		} else return root;
	}
	void update(int root) {
		a[root].size = 1;
		if (a[root].lc) a[root].size += a[a[root].lc].size;
		if (a[root].rc) a[root].size += a[a[root].rc].size;
		if (a[root].lc && a[root].rc) {
			a[root].res = F(a[a[root].lc].res, a[a[root].rc].res, a[root].type);
		}
	}
	pair <int, int> split(int root, int cnt) {
		if (cnt == 0) return make_pair(0, root);
		if (cnt == a[root].size) return make_pair(root, 0);
		root = pushdown(root);
		if (cnt <= a[a[root].lc].size) {
			int ans = ++size;
			a[ans] = a[root];
			pair <int, int> tmp = split(a[root].lc, cnt);
			a[ans].lc = tmp.second, update(ans);
			return make_pair(tmp.first, ans);
		} else {
			int ans = ++size;
			a[ans] = a[root];
			pair <int, int> tmp = split(a[root].rc, cnt - 1 - a[a[root].lc].size);
			a[ans].rc = tmp.first, update(ans);
			return make_pair(ans, tmp.second);
		}
	}
	int merge(int x, int y) {
		if (x == 0 || y == 0) return x + y;
		x = pushdown(x);
		y = pushdown(y);
		if (a[x].type < a[y].type || (a[x].type == a[y].type && a[x].size > a[y].size)) {
			int ans = ++size; a[ans] = a[x];
			a[ans].rc = merge(a[ans].rc, y);
			update(ans);
			return ans;
		} else {
			int ans = ++size; a[ans] = a[y];
			a[ans].lc = merge(x, a[ans].lc);
			update(ans);
			return ans;
		}
	}
	int build(int l, int r, const Data *v, const int *op) {
		if (l == r) {
			a[++size] = (Node) {0, 0, MAXK, 1, v[l], false};
			return size;
		} else {
			int mid = (l + r + 1) / 2, res = size + 1;
			a[++size] = (Node) {0, 0, op[mid], 1, v[mid], false};
			return merge(build(l, mid - 1, v, op), merge(res, build(mid, r, v, op)));
		}
	}
	int init(int n, const Data *v, const int *op) {
		t = v[0];
		return build(0, n - 1, v, op);
	}
	int modify(int root, int pos, Data x) {
		int rootl = split(root, pos - 1).first;
		int rootr = split(root, pos).second;
		a[++size] = (Node) {0, 0, MAXK, 1, x, false};
		int res = size;
		return merge(rootl, merge(res, rootr));
	}
	int modify(int root, int pos, int x) {
		int rootl = split(root, pos - 1).first;
		int rootr = split(root, pos).second;
		a[++size] = (Node) {0, 0, x, 1, t, false};
		int res = size;
		return merge(rootl, merge(res, rootr));
	}
	int reverse(int root, int l, int r) {
		pair <int, int> tmp = split(root, l - 1);
		int rootl = tmp.first;
		tmp = split(tmp.second, r - l + 1);
		int rootr = tmp.second;
		int rootm = tmp.first;
		a[++size] = a[rootm];
		int res = size; a[res].rev ^= true;
		return merge(rootl, merge(res, rootr));
	}
} Treap;
int cnt, root[MAXN];
// precedences: 1 ~ k, larger is higher
void init(int test_id, int n, int m, int k, const Data *a, const int *op) {
	root[cnt = 0] = Treap.init(n, a, op);
}

Data modify_data(int id, int pos, Data x) {
	root[++cnt] = Treap.modify(root[id], pos * 2 + 1, x);
	return Treap.a[root[cnt]].res;
}

// modify the operator between pos and pos - 1
Data modify_op(int id, int pos, int x) {
	root[++cnt] = Treap.modify(root[id], pos * 2, x);
	return Treap.a[root[cnt]].res;
}

Data reverse(int id, int l, int r) {
	root[++cnt] = Treap.reverse(root[id], l * 2 + 1, r * 2 + 1);
	return Treap.a[root[cnt]].res;
}