#include "game.h"
//#include <iostream>
// #include <fstream>
// std::ifstream cin ("boarding.in");
// std::ofstream cout ("boarding.out");
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <tuple>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>
#include <tuple>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template <typename T, typename U>
bool emin(T &a, const U &b) { return b < a ? a = b, true : false; }
template <typename T, typename U>
bool emax(T &a, const U &b) { return b > a ? a = b, true : false; }
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef uint64_t hash_t;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const ll M = (1LL << 61) - 1;
const ll B = uniform_int_distribution<ll>(0, M - 1)(rng);
__int128 mul(ll a, ll b) { return (__int128)a * b; }
__int128 add(ll a, ll b) { return (__int128)a + b; }
ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
ll mod_add(ll a, ll b) { return add(a, b) % M; }
ll gcd2(ll x, ll y) {
if (y == 0) return x;
return gcd2(y, x % y);
}
struct node {
ll lef, rig;
ll v;
node *l, *r;
node(ll tl, ll tr) : lef(tl), rig(tr), l(NULL), r(NULL), v(0) {}
node *make(int x) {
if(x == 0) {
if(!l) l = new node(lef, (lef + rig) / 2);
return l;
} else {
if(!r) r = new node((lef + rig) / 2 + 1, rig);
return r;
}
}
};
struct seg {
ll lef, rig;
node *root;
seg *l, *r;
seg(ll tl, ll tr) : lef(tl), rig(tr), l(NULL), r(NULL), root(NULL) {}
seg *make(int x) {
if(x == 0) {
if(!l) l = new seg(lef, (lef + rig) / 2);
return l;
} else {
if(!r) r = new seg((lef + rig) / 2 + 1, rig);
return r;
}
}
node *make2() {
if(!root) root = new node(1, (ll) 1e9);
return root;
}
} *root;
ll get(node *x) { return x ? x->v : 0; }
void upd(node *x, int c, ll z) {
if(x->lef == x->rig) return void(x->v = z);
ll m = (x->lef + x->rig) / 2;
if(c <= m) upd(x->make(0), c, z);
else upd(x->make(1), c, z);
x->v = gcd2(get(x->l), get(x->r));
}
void upd(seg *x, int c, int y, ll z) {
upd(x->make2(), y, z);
if(x->lef == x->rig) return;
ll m = (x->lef + x->rig) / 2;
if(c <= m) upd(x->make(0), c, y, z);
else upd(x->make(1), c, y, z);
}
void init(int R, int C) {
root = new seg(1, (ll) 1e9);
}
void update(int P, int Q, ll K) {
upd(root, P, Q, K);
}
ll get(node *x, int rl, int rr) {
if(rr < x->lef || rl > x->rig) return 0;
if(rl <= x->lef && x->rig <= rr) return x->v;
ll ret = 0;
if(x->l) ret = gcd2(ret, get(x->l, rl, rr));
if(x->l) ret = gcd2(ret, get(x->r, rl, rr));
return ret;
}
ll get(seg *x, int rl, int rr, int y1, int y2) {
if(rr < x->lef || rl > x->rig) return 0;
if(rl <= x->lef && x->rig <= rr) {
if(x->root) return get(x->root, y1, y2);
else return 0;
}
ll ret = 0;
if(x->l) ret = gcd2(ret, get(x->l, rl, rr, y1, y2));
if(x->l) ret = gcd2(ret, get(x->r, rl, rr, y1, y2));
return ret;
}
ll calculate(int P, int Q, int U, int V) {
return get(root, P, Q, U, V);
}
