#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
//const int inf = int(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < (high); i++)
#define repp(i, low, high) for (int i = (low); i < (high); i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
inline void fast() { cin.tie(0)->sync_with_stdio(0); }
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#else
#include "game.h"
#endif
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct tnode
{
int cnt, prio, c;
ll v, acc;
tnode *l=0, *r=0;
tnode(ll v, int c) : v(v), acc(v), cnt(1), prio(rand()), c(c) {}
};
typedef tnode* pnode;
int get_cnt(pnode x) { return x ? x->cnt : 0; }
int get_acc(pnode x) { return x ? x->cnt : 0; }
void pull(pnode x)
{
if (!x) return;
x->cnt = 1 + get_cnt(x->l) + get_cnt(x->r);
x->acc = x->v;
if (x->l) x->acc = gcd2(x->acc, x->l->acc);
if (x->r) x->acc = gcd2(x->acc, x->r->acc);
}
// first i nodes go to left
void split(pnode x, pnode& l, pnode& r, int i, int add = 0)
{
if (!x) return void(l = r = 0);
int real_i = get_cnt(x->l) + add;
if (i <= real_i) split(x->l, l, x->l, i, add), r = x;
else split(x->r, x->r, r, i, add + get_cnt(x->l) + 1), l = x;
pull(x);
}
void merge(pnode& x, pnode l, pnode r)
{
if (!l || !r) x = l ? l : r;
else if (l->prio < r->prio) merge(r->l, l, r->l), x = r;
else merge(l->r, l->r, r), x = l;
pull(x);
}
// count number of nodes with c < key
int order_of_key(pnode x, int key)
{
if (!x) return 0;
if (x->c == key) return get_cnt(x->l);
else if (x->c < key) return 1 + get_cnt(x->l) + order_of_key(x->r, key);
else return order_of_key(x->l, key);
}
vector<pnode> roots;
void init(int R, int C) {
roots.resize(R, 0);
}
void update(int P, int Q, long long K) {
pnode& root = roots[P];
int ind = order_of_key(root, Q);
pnode l, mid, r;
split(root, l, r, ind);
if (order_of_key(r, Q+1))
{
split(r, mid, r, 1);
mid->v = mid->acc = K;
}
else mid = new tnode(K, Q);
merge(l, l, mid);
merge(root, l, r);
}
long long calculate(int P, int Q, int U, int V) {
ll ret = -1;
repp(i, P, U + 1)
{
pnode& root = roots[i];
int lind = order_of_key(root, Q);
int rind = order_of_key(root, V+1);
pnode l, mid, r;
split(root, mid, r, rind);
split(mid, l, mid, lind);
if (mid)
{
if (ret == -1) ret = mid->acc;
else ret = gcd2(ret, mid->acc);
}
merge(l, l, mid);
merge(root, l, r);
}
if (ret == -1) ret = 0;
return ret;
}
//
//void solve()
//{
//
//}
//
//signed main()
//{
// fast();
//
// int r, c, q;
// cin >> r >> c >> q;
// init(r, c);
// while (q--)
// {
// int t;
// cin >> t;
// if (t==1)
// {
// int a, b, c;
// cin >> a >> b >> c;
// update(a, b, c);
// }
// else
// {
// int a, b, c, d;
// cin >> a >> b >> c >> d;
// cout << calculate(a, b, c, d) << "\n";
// }
// }
//
// return 0;
//}
