#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
inline ll gcd(const ll &a, const ll &b) { return (!b ? a : gcd(b, a % b)); }
struct node {
node *l = nullptr;
node *r = nullptr;
int p;
pii key;
ll val, g;
node(const pii &key, const ll &x) : key(key), val(x), g(x) { p = rng() % INT_MAX; }
}; typedef node* nd;
inline ll val(nd t) { return !t ? 0 : t->val; }
inline ll g(nd t) { return !t ? 0 : t->g; }
inline void upd(nd t) { if (!t) return; t->g = gcd(gcd(g(t->l), g(t->r)), t->val); }
inline nd mg(nd a, nd b) {
if (!a || !b) return !a ? b : a;
if (a->p > b->p) { a->r = mg(a->r, b); upd(a); return a; }
else { b->l = mg(a, b->l); upd(b); return b; }
}
inline pair<nd,nd> sp(nd t, pii x) {
if (!t) return {nullptr,nullptr};
if (t->key <= x) { auto tt = sp(t->r, x); t->r = tt.fi; upd(t); return {t, tt.se}; }
else { auto tt = sp(t->l, x); t->l = tt.se; upd(t); return {tt.fi, t}; }
}
inline void ins(nd &t, pii pos, ll x) {
auto [t1, t2] = sp(t, mpp(pos.fi, pos.se - 1));
auto [t3, t4] = sp(t2, pos);
t = mg(mg(t1, new node(pos, x)), t4);
}
inline ll get1(nd &t, int l, int r) {
auto [t1, t2] = sp(t, mpp(l - 1, iinf));
auto [t3, t4] = sp(t2, mpp(r, iinf));
ll res = g(t3);
t = mg(t1, mg(t3, t4));
return res;
}
struct Node {
Node *l = nullptr;
Node *r = nullptr;
nd st = nullptr;
Node() {}
}; Node *t = new Node();
inline void upd(Node *&v, int vl, int vr, int x, int y, ll d) {
if (!v) v = new Node();
ins(v->st, mpp(y, x), d);
if (vl == vr) return;
int m = vl + vr >> 1;
if (x <= m) upd(v->l, vl, m, x, y, d);
else upd(v->r, m + 1, vr, x, y, d);
}
inline ll get(Node *v, int vl, int vr, int lx, int rx, int ly, int ry) {
if (lx > rx || !v) return 0ll;
else if (vl == lx && vr == rx) return get1(v->st, ly, ry);
int m = vl + vr >> 1;
return gcd(get(v->l,vl,m,lx,min(rx,m),ly,ry),
get(v->r,m+1,vr,max(lx,m+1),rx,ly,ry));
}
int l1, r1;
void init(int R, int C) {
l1 = 0, r1 = R - 1;
}
void update(int P, int Q, long long K) {
upd(t, l1, r1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return get(t, l1, r1, P, U, Q, V);
}
