#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;
const int mxN = 1e5+1, oo = 1e9;
int c;
ll ans=0;
struct node2 {
int pos=-1,len;
ll g=0,lazy=0;
node2 *l=NULL, *r = NULL;
node2(int n) : len(n) {}
static ll total(node2* nd) {
return nd?gcd(nd->g,nd->lazy):0LL;
}
void query(int a, int b) {
if(b<0 or a>=len) return;
if(a<=0 and b>=len-1) {
ans = gcd(ans,g);
ans = gcd(ans,lazy);
}
if(pos!=-1 and a<=pos and pos<=b) {
ans = gcd(ans,lazy);
}
int mid = len/2;
if(l) l->query(a,b);
if(r) r->query(a-mid,b-mid);
}
void update(int y, ll v) {
if(pos==-1) {
pos=y;
lazy=v;
return;
}
if(y==pos) {
lazy=v;
return;
}
int 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) {
if(dd<0 or cc>=len) return;
int mid = len/2;
if(cc<=0 and dd>=len-1) {
if(sub) sub->query(a,b);
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) {
int mid = len/2;
if(!sub) sub = new node2(c);
sub->update(y,v);
if(len==1) return;
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;
void init(int R, int C) {
c=C;
root = node(R);
}
void update(int P, int Q, long long 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);
return ans;
}
