#include "game.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
int R, C;
ll gcd(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Seg {
int bg, ed;
ll val;
Seg* ls=nullptr;
Seg* rs=nullptr;
Seg(int l, int r, ll v=0) {
bg=l; ed=r; val=v;
}
ll f(Seg* s) {
if(s == nullptr) return 0;
return s->val;
}
ll f(Seg* s, int i, int j, int l, int r) {
if(s == nullptr) return 0;
return s->get(i,j,l,r);
}
void set(int i, ll v, int l, int r) {
int m=(l+r)/2;
if(bg == ed) {
if(i == bg) {
val = v;
return;
} else {
int j = bg;
bg = l; ed = r;
if(j <= m) {
ls = new Seg(j,j,val);
} else {
rs = new Seg(j,j,val);
}
}
}
if(i <= m) {
if(ls == nullptr) ls = new Seg(i,i);
ls->set(i,v,l,m);
} else {
if(rs == nullptr) rs = new Seg(i,i);
rs->set(i,v,m+1,r);
}
val = gcd(f(ls), f(rs));
}
ll get(int i, int j, int l, int r) {
if(j < bg || i > ed) return 0;
if(i <= bg && j >= ed) return val;
int m=(l+r)/2;
ll a = f(ls,i,j,l,m);
ll b = f(rs,i,j,m+1,r);
return gcd(a,b);
}
};
struct Seg2 {
int bg, ed;
Seg val;
Seg2* ls=nullptr;
Seg2* rs=nullptr;
Seg2(int l, int r) : val(0,C-1) {
bg = l; ed = r;
}
ll f(Seg2* s, int j) {
if(s == nullptr) return 0;
return s->val.get(j,j,0,C-1);
}
void set(int i, int j, ll v, int l, int r) {
int m=(l+r)/2;
if(l == r) {
val.set(j,v,0,C-1);
return;
}
if(i <= m) {
if(ls == nullptr) ls = new Seg2(l,m);
ls->set(i,j,v,l,m);
} else {
if(rs == nullptr) rs = new Seg2(m+1,r);
rs->set(i,j,v,m+1,r);
}
ll nV = 0;
nV = gcd(f(ls,j), f(rs,j));
val.set(j,nV,0,C-1);
}
ll f(Seg2* s, int i, int j, int I, int J, int l, int r) {
if(s == nullptr) return 0;
return s->get(i,j,I,J,l,r);
}
ll get(int i, int j, int I, int J, int l, int r) {
if(j < l || i > r) return 0;
if(i <= l && j >= r) return val.get(I,J,0,C-1);
int m=(l+r)/2;
ll a = f(ls,i,j,I,J,l,m);
ll b = f(rs,i,j,I,J,m+1,r);
return gcd(a,b);
}
};
Seg2* SEG;
void init(int _R, int _C) {
R = _R;
C = _C;
SEG = new Seg2(0,R-1);
//RE(i,R) SEG[i] = new Seg(0,C-1);
}
void update(int P, int Q, ll K) {
SEG->set(P,Q,K,0,R-1);
//SEG[P]->set(Q,K,0,C-1);
}
ll calculate(int P, int Q, int U, int V) {
/*ll ans = 0;
REP(i,P,U+1) ans = gcd(ans, SEG[i]->get(Q,V,0,C-1));
return ans;*/
return SEG->get(P,U,Q,V,0,R-1);
}
