#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
const ll value=3000000000;
using namespace std;
ll x,y,k,x_,y_;
unordered_map<ll,ll>t;
long long gcd2(long long X, long long Y) {
if(Y>X) swap(X,Y);
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void updateY(ll vx, ll lx, ll rx, ll vy, ll ly, ll ry) {
if (ly == ry) {
if (lx == rx){
t[vx*value+vy] = k;
}
else{
t[vx*value+vy] = gcd2(t[vx*2*value+vy],t[(vx*2+1)*value+vy]);
// cout << t[vx*2*value+vy] << '\n';
}
} else {
ll my = (ly + ry) / 2;
if(my>=y) updateY(vx, lx, rx, vy*2, ly, my);
else updateY(vx, lx, rx, vy*2+1, my+1, ry);
t[vx*value+vy] = gcd2(t[vx*value+vy*2],t[vx*value+vy*2+1]);
}
// cout << t[vx*value+vy] << ' ' << lx << ' ' << rx << ' ' << ly << ' ' << ry << '\n';
}
void updateX(ll vx, ll lx, ll rx) {
if (lx != rx) {
ll mx = (lx + rx) / 2;
if(mx>=x) updateX(vx*2, lx, mx);
else updateX(vx*2+1, mx+1, rx);
}
updateY(vx, lx, rx, 1, 0, 1000000000);
}
void init(int R, int C) {
/* ... */
}
void update(int P, int Q, long long K) {
x=P;
y=Q;
k=K;
updateX(1,0,1000000000);
}
ll queryY(ll idx,ll L,ll R,ll idy,ll l,ll r) {
if(r<y || y_<l) return 0;
if(y<=l && r<=y_){
return t[idx*value+idy];
}
ll m=l+r>>1;
return gcd2(queryY(idx,L,R,idy*2,l,m),queryY(idx,L,R,idy*2+1,m+1,r));
}
ll queryX(ll id,ll l,ll r) {
if(r<x || x_<l) return 0;
if(x<=l && r<=x_) return queryY(id,l,r,1,0,1000000000);
ll m=l+r>>1;
return gcd2(queryX(id*2,l,m),queryX(id*2+1,m+1,r));
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
x=P;
y=Q;
x_=U;
y_=V;
return queryX(1,0,1000000000);
}
