#include "game.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
ll r,c;
ll ans=0;
struct node2 {
ll pos=-1,len;
ll g=0,lazy=0;
node2 *l=NULL, *r = NULL;
node2(ll n) : len(n) {}
static ll total(node2* nd) {
return nd?gcd(nd->g,nd->lazy):0LL;
}
void query(ll a, ll b) const {
if(b<0 or a>=len) return;
if(pos!=-1 and a<=pos and pos<=b) ans = gcd(ans,lazy);
if(a<=0 and b>=len-1) {
ans = gcd(ans,g);
return;
}
ll mid = len/2;
if(l) l->query(a,b);
if(r) r->query(a-mid,b-mid);
}
void update(ll y, ll v) {
if(y==pos or pos==-1) {
pos = y;
lazy=v;
return;
}
ll mid = len/2;
if(y<mid) {
if(!l) l = new node2(mid);
l->update(y,v);
} else {
if(!r) r = new node2(len-mid);
r->update(y-mid,v);
}
g = gcd(total(l),total(r));
}
};
struct node {
node *l = NULL, *r = NULL;
int len; // make it power of 2?
node2 *sub = NULL;
node(int n) : len(n) {}
node() {}
void query(int cc, int dd, int a,int b) const {
if(dd<0 or cc>=len) return;
int mid = len/2;
if(cc<=0 and dd>=len-1) {
if(sub) sub->query(a*::r,b*::r+::r-1);
return;
}
if(l) l->query(cc,dd,a,b);
if(r) r->query(cc-mid,dd-mid,a,b);
}
void update(int x, int y, ll v) {
if(!sub) sub = new node2(c*::r);
sub->update(y*::r + x,v);
if(len==1) return;
int mid = len/2;
if(x<mid) {
if(!l) l = new node(mid);
l->update(x,y,v);
} else {
if(!r) r = new node(len-mid);
r->update(x-mid,y,v);
}
}
} root;
vvi a;
void init(int R, int C) {
r=R,c=C;
// a.assign(R,vi(C));
root = node(R);
}
vi queries;
void update(int P, int Q, long long K) {
// cout << "1 " << P << ' ' << Q << ' ' << K << '\n';
// a[P][Q]=K;
root.update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
ans=0;
root.query(P,U,Q,V);
// cout << "2 " << P << ' ' << Q << ' ' << U << ' ' << V << '\n';
// ll bans=0;
// for(int i=P;i<=U;++i) {
// for(int j=Q;j<=V;++j) {
// bans=gcd(bans,a[i][j]);
// }
// }
// if(ans!=bans) {
// exit(0);
// }
return ans;
}
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<class I> I rnd(I l,I r){return std::uniform_int_distribution<I>(l,r)(rng);}
#ifdef LOCALfg
int main() {
while(true) {
int R = rnd(2,4),C = rnd(2,4);
cout << "TEST!\n";
cout << R << ' '<< C << '\n';
init(R,C);
for(int i=0;i<6;++i) {
if(rnd(0,1)==0) {
update(rnd(0,R-1),rnd(0,C-1), rnd(0,50));
} else {
auto get = [&](int B) {
int l=rnd(0,B-1),r=rnd(0,B-1);
if(l>r) swap(l,r);
return pi{l,r};
};
auto [P,U] = get(R);
auto [Q,V] = get(C);
calculate(P,Q,U,V);
}
}
}
}
#endif
