#include "game.h"
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
#include <bits/stdc++.h>
using namespace std;
struct Node{
long long val;
Node *l;
Node *r;
Node (){
val=0;
l=nullptr;
r=nullptr;
}
};
struct SegmentTree{
Node *root;
SegmentTree(){
root=new Node();
}
void update(Node *t, int l, int r, int pos, long long val){
if (l==r){
t->val=val;
return;
}
if (!t->l) t->l=new Node();
if (!t->r) t->r=new Node();
int mid=(l+r)>>1;
if (pos<=mid) update(t->l, l, mid, pos, val);
else update(t->r, mid+1, r, pos, val);
t->val=gcd2(t->l->val, t->r->val);
}
long long get(Node *t, int l, int r, int L, int R){
if (r<L || R<l) return 0;
if (L<=l && r<=R) return t->val;
if (!t->l || !t->r) return 0;
int mid=(l+r)>>1;
return gcd2(get(t->l, l, mid, L, R), get(t->r, mid+1, r, L, R));
}
};
int sz;
SegmentTree st[2000000];
map<int, int> mp;
long long t[8010][8010];
int R, C;
long long sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
if (ly > ry)
return 0;
if (ly == tly && try_ == ry)
return t[vx][vy];
int tmy = (tly + try_) >> 1;
return gcd2(sum_y(vx, vy<<1, tly, tmy, ly, min(ry, tmy)),
sum_y(vx, vy<<1|1, tmy+1, try_, max(ly, tmy+1), ry));
}
long long sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
if (lx > rx)
return 0;
if (lx == tlx && trx == rx)
return sum_y(vx, 1, 1, C, ly, ry);
int tmx = (tlx + trx) >> 1;
return gcd2(sum_x(vx<<1, tlx, tmx, lx, min(rx, tmx), ly, ry),
sum_x(vx<<1|1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry));
}
void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, long long new_val) {
if (ly == ry) {
if (lx == rx)
t[vx][vy] = new_val;
else
t[vx][vy] = gcd2(t[vx<<1][vy], t[vx<<1|1][vy]);
} else {
int my = (ly + ry) >> 1;
if (y <= my)
update_y(vx, lx, rx, vy<<1, ly, my, x, y, new_val);
else
update_y(vx, lx, rx, vy<<1|1, my+1, ry, x, y, new_val);
t[vx][vy] = gcd2(t[vx][vy<<1], t[vx][vy<<1|1]);
}
}
void update_x(int vx, int lx, int rx, int x, int y, long long new_val) {
if (lx != rx) {
int mx = (lx + rx) >> 1;
if (x <= mx)
update_x(vx<<1, lx, mx, x, y, new_val);
else
update_x(vx<<1|1, mx+1, rx, x, y, new_val);
}
update_y(vx, lx, rx, 1, 1, C, x, y, new_val);
}
void init(int _R, int _C) {
R=_R; C=_C;
}
void update(int P, int Q, long long K) {
++P; ++Q;
if (R<=2000 && C<=2000){
update_x(1, 1, R, P, Q, K);
return;
}
if (!mp.count(P)){
mp[P]=sz++;
}
int id=mp[P];
st[id].update(st[id].root, 1, 1e9, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
++P; ++Q; ++U; ++V;
if (R<=2000 && Q<=2000) return sum_x(1, 1, R, P, U, Q, V);
long long ans=0;
for (auto it=mp.lower_bound(P); it!=mp.end(); ++it){
if (it->first>U) continue;
ans=gcd2(ans, st[it->second].get(st[it->second].root, 1, 1e9, Q, V));
}
return ans;
}
