#include <bits/stdc++.h>
using namespace std;
#include "game.h"
struct segtree_t {
vector<long long> segtree; vector<int> A; int n;
segtree_t(){}
segtree_t(segtree_t x,segtree_t y){
merge(x.A.begin(),x.A.end(),y.A.begin(),y.A.end(),back_inserter(A));
n = A.size(),segtree.resize(2*n);
for (int i(0),a(0),b(0);i < n;++i){
if (a!=x.A.size()&&x.A[a]==A[i]) segtree[n+i] = gcd(segtree[n+i],x.segtree[x.n+a++]);
if (b!=y.A.size()&&y.A[b]==A[i]) segtree[n+i] = gcd(segtree[n+i],y.segtree[y.n+b++]);
}
for (int i(n-1);i;--i) segtree[i] = gcd(segtree[i<<1],segtree[i<<1|1]);
}
void push(int x,long long y){
A.emplace_back(x),segtree.emplace_back(y);
}
void build(){
n = A.size();
segtree.resize(2*n);
copy(segtree.begin(),segtree.begin()+n,segtree.begin()+n);
for (int i(n-1);i;--i) segtree[i] = gcd(segtree[i<<1],segtree[i<<1|1]);
}
void update(int x,long long y){
x = lower_bound(A.begin(),A.end(),x)-A.begin()+n;
segtree[x] = y;
for (x>>=1;x;x>>=1) segtree[x] = gcd(segtree[x<<1],segtree[x<<1|1]);
}
long long query(int ll,int rr){
int l = lower_bound(A.begin(),A.end(),ll)-A.begin();
int r = lower_bound(A.begin(),A.end(),rr)-A.begin();
long long res(0);
for (l+=n,r+=n;l < r;l>>=1,r>>=1){
if (l&1) res = gcd(res,segtree[l++]);
if (r&1) res = gcd(res,segtree[--r]);
}
return res;
}
};
int h,w,n,q;
vector<segtree_t> segtree;
vector<pair<pair<int,int>,long long>> A;
map<pair<int,int>,pair<long long,int>> M;
vector<int> Z;
void rebuild(){
Z.clear();
for (auto [a,b]:M) if (Z.empty()||Z.back()!=a.first) Z.emplace_back(a.first);
n = Z.size();
segtree.assign(2*n,segtree_t());
for (auto [a,b]:M){
int x = lower_bound(Z.begin(),Z.end(),a.first)-Z.begin()+n;
segtree[x].push(a.second,b.first);
}
for (int i(0);i < n;++i) segtree[n+i].build();
for (int i(n-1);i;--i) segtree[i] = segtree_t(segtree[i<<1],segtree[i<<1|1]);
}
void init(int H,int W){
h = H,w = W,n = 0,q = 0;
}
void update(int x,int y,long long z){
int p = A.size();
if (M.contains(make_pair(x,y))){
auto& [a,b] = M[make_pair(x,y)];
int l = lower_bound(Z.begin(),Z.end(),x)-Z.begin()+n;
long long t = z;
if (b/149!=(p-1)/149) for (;l;l>>=1) segtree[l].update(y,t),t = gcd(t,segtree[l^1].query(y,y+1));
a = z,A[b].second = z;
} else {
M[make_pair(x,y)] = make_pair(z,A.size()),A.emplace_back(make_pair(x,y),z);
}
if (p!=A.size()&&((int)A.size())%149==0) rebuild();
}
long long calculate(int a,int b,int c,int d){
++c,++d;
int l = lower_bound(Z.begin(),Z.end(),a)-Z.begin()+n;
int r = lower_bound(Z.begin(),Z.end(),c)-Z.begin()+n;
long long res(0);
for (;l < r;l>>=1,r>>=1){
if (l&1) res = gcd(res,segtree[l++].query(b,d));
if (r&1) res = gcd(res,segtree[--r].query(b,d));
}
for (int i(A.size()/149*149);i < (int)A.size();++i){
auto [e,f] = A[i];
if (a<=e.first&&e.first<c&&b<=e.second&&e.second<d) res = gcd(res,f);
}
return res;
}
