#include "game.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
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;
}
struct node{
ll tl, tr, val;
node *l = nullptr, *r = nullptr;
node(ll tlval, ll trval){
tl = tlval;
tr = trval;
val = 0;
}
node(){}
void upd(ll idx, ll nv){
if(tl == idx && tr == idx){
val = nv;
return;
}
ll tm = (tl+tr)/2;
if(idx <= tm){
if(!l)
l = new node(tl, tm);
l->upd(idx, nv);
}
else{
if(!r)
r = new node(tm+1, tr);
r->upd(idx, nv);
}
ll xval = 0, yval = 0;
if(l)
xval = l->val;
if(r)
yval = r->val;
val = gcd2(xval, yval);
}
ll get(ll lef, ll rig){
if(tr < lef || rig < tl)
return 0;
if(lef <= tl && tr <= rig){
return val;
}
ll xval = 0, yval = 0;
if(l)
xval = l->get(lef, rig);
if(r)
yval = r->get(lef, rig);
return gcd2(xval, yval);
}
};
ll r, c;
struct seg{
ll tl, tr;
node *val;
seg *l = nullptr, *r = nullptr;
seg(ll tval, ll rval){
tl = tval;
tr = rval;
val = new node(0, c-1);
}
seg(){}
void upd(ll xidx, ll yidx, ll nv){
val->upd(yidx, nv);
if(tl == xidx && tr == xidx){
return;
}
ll tm = (tl+tr)/2;
if(xidx <= tm){
if(!l)
l = new seg(tl, tm);
l->upd(xidx, yidx, nv);
}
else{
if(!r)
r = new seg(tm+1, tr);
r->upd(xidx, yidx, nv);
}
}
ll get(ll xl, ll xr, ll yl, ll yr){
if(tr < xl || xr < tl)
return 0;
if(xl <= tl && tr <= xr){
return val->get(yl, yr);
}
ll xval = 0, yval = 0;
if(l)
xval = l->get(xl, xr, yl, yr);
if(r)
yval = r->get(xl, xr, yl, yr);
return gcd2(xval, yval);
}
};
seg root;
node ar[2009];
void init(int R, int C) {
r = R;
c = C;
for(int i = 0; i < r; ++i)
ar[i] = node(0, c-1);
//root = seg(0, r-1);
}
void update(int P, int Q, long long K) {
ar[P].upd(Q, K);
//root.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
ll ans = 0;
for(int i = P; i <= U; ++i)
ans = gcd2(ans, ar[i].get(Q, V));
return ans;
return root.get(P, U, Q, V);
}
