#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "game.h"
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
int R, C;
ll gcd(ll x, ll y) {
if (x == 0 || y == 0) return max(x, y);
return __gcd(x, y);
}
struct nodeY
{
int lo, hi;
nodeY *l=0, *r=0;
ll val = 0;
};
struct nodeX {
nodeX *l=0, *r=0;
nodeY *root=0;
nodeX() {
l = 0, r = 0;
root = new nodeY();
root->lo = 0, root->hi = C - 1;
}
};
nodeX *root=0;
ll qry2(nodeY *cur, int yL, int yH) {
if (!cur) return 0;
if (yH < cur->lo || cur->hi < yL) return 0;
if (yL <= cur->lo && cur->hi <= yH) return cur->val;
return gcd(qry2(cur->l, yL, yH), qry2(cur->r, yL, yH));
}
ll qry1(nodeX *cur, int l, int r, int xL, int xH, int yL, int yH) {
if (!cur) return 0;
if (r < xL || xH < l) return 0;
if (xL <= l && r <= xH) return qry2(cur->root, yL, yH);
int m = (l + r) / 2;
return gcd(qry1(cur->l, l, m, xL, xH, yL, yH), qry1(cur->r, m+1, r, xL, xH, yL, yH));
}
void upd2(nodeY *cur, int y, ll val) {
if (cur->lo == cur->hi) {
cur->val = val;
return;
}
int m = (cur->lo + cur->hi) / 2;
if (y <= m) {
if (!cur->l) {
cur->l = new nodeY();
cur->l->lo = cur->lo;
cur->l->hi = m;
cur->l->val = val;
}
upd2(cur->l, y, val);
} else {
if (!cur->r) {
cur->r = new nodeY();
cur->r->lo = m + 1;
cur->r->hi = cur->hi;
cur->r->val = val;
}
upd2(cur->r, y, val);
}
ll a = 0, b = 0;
if (cur->l) a = cur->l->val;
if (cur->r) b = cur->r->val;
cur->val = gcd(a, b);
}
void upd1(int l, int r, nodeX *cur, int x, int y, ll val) {
if (l == r) {
upd2(cur->root, y, val);
return;
}
int m = (l + r) / 2;
ll a = 0, b = 0;
if (x <= m) {
if (!cur->l) cur->l = new nodeX();
upd1(l, m, cur->l, x, y, val);
} else {
if (!cur->r) cur->r = new nodeX();
upd1(m+1, r, cur->r, x, y, val);
}
if (cur->l) a = qry2(cur->l->root, y, y);
if (cur->r) b = qry2(cur->r->root, y, y);
upd2(cur->root, y, gcd(a, b));
}
void init(int R1, int C1) {
R = R1, C = C1;
root = new nodeX();
}
void update(int p, int q, ll k) {
upd1(0, R-1, root, p, q, k);
}
ll calculate(int p, int q, int u, int v) {
return qry1(root, 0, R-1, p, u, q, v);
}
