// In the name of Allah
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m;
const int maxs = 1e7 + 4;
ll t[maxs]; int tx[maxs];
int lc[maxs], rc[maxs], sz;
void set_val(int v, int u1, int u2, int tl, int tr, int i, int j, ll x) {
if (tr - tl == 1) {
if (tx[v] == -1) {
t[v] = 0;
if (u1 == -1 && u2 == -1) t[v] = x;
else {
if (u1 != -1) t[v] = __gcd(t[v], t[u1]);
if (u2 != -1) t[v] = __gcd(t[v], t[u2]);
}
}
else {
set_val(tx[v], -1, -1, 0, m, j, -1, x);
}
return ;
}
int mid = (tl + tr) / 2;
if (i < mid) {
if (lc[v] == -1) {
int u = sz++; lc[v] = u;
if (tx[v] != -1) tx[u] = sz++;
}
int x1 = u1, x2 = u2;
if (x1 != -1) x1 = lc[x1];
if (x2 != -1) x2 = lc[x2];
set_val(lc[v], x1, x2, tl, mid, i, j, x);
}
else {
if (rc[v] == -1) {
int u = sz++; rc[v] = u;
if (tx[v] != -1) tx[u] = sz++;
}
int x1 = u1, x2 = u2;
if (x1 != -1) x1 = rc[x1];
if (x2 != -1) x2 = rc[x2];
set_val(rc[v], x1, x2, mid, tr, i, j, x);
}
t[v] = 0;
if (tx[v] == -1) {
if (lc[v] != -1) t[v] = __gcd(t[v], t[lc[v]]);
if (rc[v] != -1) t[v] = __gcd(t[v], t[rc[v]]);
}
else {
int x1 = -1, x2 = -1;
if (lc[v] != -1) x1 = tx[lc[v]];
if (rc[v] != -1) x2 = tx[rc[v]];
set_val(tx[v], x1, x2, 0, m, j, -1, x);
}
}
ll get_val(int v, int tl, int tr, int l, int r, int lx, int rx) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return 0;
if (l == tl && r == tr) {
if (tx[v] != -1) {
return get_val(tx[v], 0, m, lx, rx, -1, -1);
}
else return t[v];
}
ll res = 0; int mid = (tl + tr) / 2;
if (lc[v] != -1) res = __gcd(res, get_val(lc[v], tl, mid, l, r, lx, rx));
if (rc[v] != -1) res = __gcd(res, get_val(rc[v], mid, tr, l, r, lx, rx));
return res;
}
void init(int R, int C) {
n = R; m = C;
fill(tx, tx + maxs, -1);
fill(lc, lc + maxs, -1); fill(rc, rc + maxs, -1);
sz = 1; tx[0] = sz++;
return ;
}
void update(int i, int j, ll x) {
set_val(0, -1, -1, 0, n, i, j, x);
}
ll calculate(int l1, int l2, int r1, int r2) {
r1++; r2++;
return get_val(0, 0, n, l1, r1, l2, r2);
}
