#pragma GCC optimize ("O3")
#include "game.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXR = 1e9;
const int MAXC = 1e9;
const int MAX = 5e6;
ll gcd(ll a, ll b) {
if (!b) return a;
else return gcd(b, a % b);
}
ll tree[MAX];
int L[MAX], R[MAX], root[MAX], lazyPos[MAX];
int nxtFree = 1;
/// Here lazyPos is used to optimize memory.
/// When there is only one updated position in the range, we stop at that node and don't create new nodes down
void relax(int v, int l, int r) {
int mid = (l + r) >> 1;
if (lazyPos[v] <= mid) {
L[v] = ++nxtFree;
tree[L[v]] = tree[v];
lazyPos[L[v]] = lazyPos[v];
} else {
R[v] = ++nxtFree;
tree[R[v]] = tree[v];
lazyPos[R[v]] = lazyPos[v];
}
lazyPos[v] = 0;
}
void update1D(int v, int l, int r, int pos, ll val) {
if (l == r) {
tree[v] = val;
} else {
if (lazyPos[v]) {
if (lazyPos[v] == pos) {
tree[v] = val;
} else {
relax(v, l, r);
}
}
int mid = (l + r) >> 1;
if (pos <= mid) {
if (!L[v]) {
L[v] = ++nxtFree;
tree[L[v]] = val;
lazyPos[L[v]] = pos;
} else {
update1D(L[v], l, mid, pos, val);
}
} else {
if (!R[v]) {
R[v] = ++nxtFree;
tree[R[v]] = val;
lazyPos[R[v]] = pos;
} else {
update1D(R[v], mid + 1, r, pos, val);
}
}
ll gcdL = 0, gcdR = 0;
if (L[v]) gcdL = tree[L[v]];
if (R[v]) gcdR = tree[R[v]];
tree[v] = gcd(gcdL, gcdR);
}
}
ll query1D(int v, int l, int r, int ql, int qr) {
if (ql > r || l > qr) return 0;
else if (ql <= l && r <= qr) return tree[v];
else if (lazyPos[v]) return (ql <= lazyPos[v] && lazyPos[v] <= qr) ? tree[v] : 0;
else {
int mid = (l + r) >> 1;
ll gcdL = 0, gcdR = 0;
if (L[v]) gcdL = query1D(L[v], l, mid, ql, qr);
if (R[v]) gcdR = query1D(R[v], mid + 1, r, ql, qr);
return gcd(gcdL, gcdR);
}
}
void update2D(int v, int l, int r, int posR, int posC, ll val) {
if (l == r) {
if (!root[v]) root[v] = ++nxtFree;
update1D(root[v], 1, MAXC, posC, val);
} else {
int mid = (l + r) >> 1;
if (posR <= mid) {
if (!L[v]) L[v] = ++nxtFree;
update2D(L[v], l, mid, posR, posC, val);
} else {
if (!R[v]) R[v] = ++nxtFree;
update2D(R[v], mid + 1, r, posR, posC, val);
}
ll gcdL = 0, gcdR = 0;
if (L[v]) gcdL = query1D(root[L[v]], 1, MAXC, posC, posC);
if (R[v]) gcdR = query1D(root[R[v]], 1, MAXC, posC, posC);
ll combinedVal = gcd(gcdL, gcdR);
if (!root[v]) root[v] = ++nxtFree;
update1D(root[v], 1, MAXC, posC, combinedVal);
}
}
ll query2D(int v, int l, int r, int rowL, int rowR, int colL, int colR) {
if (rowL > r || l > rowR) return 0;
else if (rowL <= l && r <= rowR) {
if (root[v]) return query1D(root[v], 1, MAXC, colL, colR);
else return 0;
} else {
int mid = (l + r) >> 1;
ll gcdL = 0, gcdR = 0;
if (L[v]) gcdL = query2D(L[v], l, mid, rowL, rowR, colL, colR);
if (R[v]) gcdR = query2D(R[v], mid + 1, r, rowL, rowR, colL, colR);
return gcd(gcdL, gcdR);
}
}
void init(int R, int C) {
}
void update(int P, int Q, ll K) {
++P;
++Q;
update2D(1, 1, MAXR, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
++P;
++Q;
++U;
++V;
return query2D(1, 1, MAXR, P, U, Q, V);
}
