#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, pos, p, v;
ll perm;
node *l, *r;
node(ll tp, ll tv) : lef(tp), rig(tp), pos(tp), p(rand()), l(NULL), r(NULL), perm(tv), v(tv) {}
};
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;
}
}
} *root;
ll get(node *x) { return x ? x->v : 0; }
ll lef(node *x) { return x ? x->lef : (ll) 1e12; }
ll rig(node *x) { return x ? x->rig : (ll) -1e12; }
void pop(node *x) {
if(!x) return;
x->v = gcd2(x->perm, gcd2(get(x->l), get(x->r)));
x->lef = min(x->pos, lef(x->l));
x->rig = max(x->pos, rig(x->r));
}
void split(node *x, node *&l, node *&r, int pos) {
if(!x) return void(l = r = NULL);
if(x->pos <= pos) split(x->r, x->r, r, pos), l = x;
else split(x->l, l, x->l, pos), r = x;
pop(x);
}
void merge(node *&x, node *l, node *r) {
if(!l || !r) x = l ? l : r;
else if(l->p > r->p) merge(l->r, l->r, r), x = l;
else merge(r->l, l, r->l), x = r;
pop(x);
}
void upd(node *&x, int pos, ll z) {
node *a, *b, *c;
split(x, a, b, pos - 1);
split(b, b, c, pos);
merge(a, a, new node(pos, z));
merge(x, a, c);
}
ll get(node *&x, int rl, int rr) {
node *a, *b, *c;
split(x, a, b, rl - 1);
split(b, b, c, rr);
ll ret = get(b);
merge(x, a, b);
merge(x, x, c);
return ret;
}
void upd(seg *x, int c, int y, ll z) {
if(x->lef == x->rig) { upd(x->root, y, z); 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);
ll nz = gcd2(x->l ? get(x->l->root, y, y) : 0, x->r ? get(x->r->root, y, y) : 0);
upd(x->root, y, nz);
}
ll get(seg *x, int rl, int rr, int y1, int y2) {
if(!x || rr < x->lef || rl > x->rig) return 0;
if(rl <= x->lef && x->rig <= rr) return get(x->root, y1, y2);
return gcd2(get(x->l, rl, rr, y1, y2), get(x->r, rl, rr, y1, y2));
}
void init(int R, int C) {
root = new seg(0, (ll) 1e9);
}
void update(int P, int Q, ll K) {
upd(root, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return get(root, P, U, Q, V);
}
// int main() {
// int R, C, N;
// cin >> R >> C >> N;
// init(R, C);
// for(int i = 0; i < N; i++) {
// int w;
// cin >> w;
// if(w == 1) {
// ll P, Q, K;
// cin >> P >> Q >> K;
// update(P, Q, K);
// } else {
// int P, Q, U, V;
// cin >> P >> Q >> U >> V;
// cout << calculate(P, Q, U, V) << endl;
// }
// }
// }
