#include "expr.h"
using namespace std;
#include <vector>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <iostream>
// #include "grader.cpp"
using namespace std;
// precedences: 1 ~ k, larger is higher
struct dsu {
	int n;
	vector<int> fa;
	dsu(int _n): n(_n), fa(_n) { iota(fa.begin(), fa.end(), 0); }
	int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
};
int fun(int a, int b, int op) {
	Data A;
	A.x = a;
	Data B;
	B.x = b;
	return F(A, B, op).x;
}
int testid, N, M, K;
vector<int> A, Ops;
namespace sub2{
const int Block=200;
int lef[666],rgt[666],tot;
int sm[666];
int bel[22222];
void gs(int id) {
	sm[id] = -1;
	for(int i=lef[id]; i<=rgt[id]; ++i)
		if(sm[id] == -1)sm[id] = A[i];
		else sm[id] = fun(sm[id], A[i],1);
}
void init() {
	for(int l=0,r;l<N;l=r+1){
		r = min(N-1, l+Block);
		++tot,lef[tot] = l,rgt[tot] = r;
		gs(tot);
		for(int i = l; i <= r; ++i)bel[i] = tot;
	}
}
int getans(){
//to do
	int s=-1;
	for(int i=1;i<=tot;++i)
		if(s == -1)s = sm[i];
		else s = fun(s,sm[i],1);
	return s;
}
}
int calcval(vector<int> a, vector<int> ops) {
	// to do
	vector<int> va = a;
	vector<tuple<int, int, int>> xl;
	for (int i = 1; i < N; ++i)
		xl.emplace_back(ops[i], i - 1, i);
	dsu d(N);
	sort(xl.rbegin(), xl.rend());
	for (auto [op, lef, rgt]: xl)
		lef = d.find(lef), va[lef] = fun(va[lef], va[rgt], op), d.fa[rgt] = lef;
	return va[0];
}
namespace sub1 {
vector<int> ha[11111], hops[11111];
int tot;
}
void init(int test_idtest_id, int nn, int mm, int kk, const Data *aa, const int *opsops)
{
	testid = test_idtest_id;
	N = nn;
	M = mm;
	K = kk;
	A.resize(N);
	for (int i = 0; i < N; ++i)
		A[i] = aa[i].x;
	Ops.resize(N);
	for (int i = 1; i < N; ++i)
		Ops[i] = opsops[i];
	sub1::ha[0] = A;
	sub1::hops[0] = Ops;
	if(testid==3||testid==4) {
		sub2::init();
	}
}

Data modify_data(int id, int pos, Data xx)
{
	Data ret;
	int x = xx.x;
	if (testid <= 2) {
		using namespace sub1;
		++tot;
		ha[sub1::tot] = ha[id];
		hops[sub1::tot] = hops[id];
		ha[sub1::tot][pos] = x;
		int zhi = calcval(ha[sub1::tot], hops[sub1::tot]);
		ret.x = zhi;
	}
	if(testid == 3 || testid==4){
		// using namespace sub2;
		A[id] = x;
		sub2::gs(sub2::bel[id]);
		ret.x = sub2::getans();
	}
	return ret;
}

// modify the operator between pos and pos - 1
Data modify_op(int id, int pos, int new_op)
{
	Data ret;
	if (testid <= 2) {
		using namespace sub1;
		++sub1::tot;
		ha[sub1::tot] = ha[id];
		hops[sub1::tot] = hops[id];
		hops[sub1::tot][pos] = new_op;
		int zhi = calcval(ha[sub1::tot], hops[sub1::tot]);
		ret.x = zhi;
	}
	if(testid == 3 || testid == 4)ret.x = sub2::getans();
	return ret;
}

Data reverse(int id, int l, int r)
{
	Data ret;
	if (testid <= 2) {
		using namespace sub1;
		++sub1::tot;
		ha[sub1::tot] = ha[id];
		hops[sub1::tot] = hops[id];
		reverse(ha[sub1::tot].begin() + l, ha[sub1::tot].begin() + r + 1);
		reverse(hops[sub1::tot].begin() + l + 1, hops[sub1::tot].begin() + r + 1);
		int zhi = calcval(ha[sub1::tot], hops[sub1::tot]);
		ret.x = zhi;
	}
	if(testid == 3 || testid == 4)ret.x = sub2::getans();
	return ret;
}