#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
struct segTree1d{
struct Node{
Node *lc, *rc;
ll val; int loc; /// loc: 걸어둔 정점이면 그 위치, 아니면 0
Node(){
lc = rc = nullptr;
val = 0, loc = -1;
}
~Node(){
if(lc) delete lc;
if(rc) delete rc;
}
void update(int l, int r, int x, ll v){
if(loc != -1){
int m = (l+r)>>1;
if(loc <= m) lc = new Node(), lc->update(l, m, loc, val);
else rc = new Node(), rc->update(m+1, r, loc, val);
loc = -1;
val = __gcd(lc?lc->val:0, rc?rc->val:0);
}
if(l==r){
val = v;
return;
}
if(!val && !lc && !rc){
val = v, loc = x;
return;
}
int m = (l+r)>>1;
if(x<=m){
if(!lc) lc = new Node();
lc->update(l, m, x, v);
}
else{
if(!rc) rc = new Node();
rc->update(m+1, r, x, v);
}
val = __gcd(lc?lc->val:0, rc?rc->val:0);
}
ll query(int l, int r, int s, int e){
if(loc != -1){
if(loc < s || e < loc) return 0;
else return val;
}
if(r<s || e<l) return 0;
if(s<=l && r<=e) return val;
int m = (l+r)>>1;
return __gcd(lc ? lc->query(l, m, s, e) : 0, rc ? rc->query(m+1, r, s, e) : 0);
}
} *root;
segTree1d(){
root = new Node();
}
void update(int y, ll v){
root->update(0, m-1, y, v);
}
ll query(int yl, int yr){
return root->query(0, m-1, yl, yr);
}
};
struct segTree2d{
struct Node{
Node *lc, *rc;
segTree1d tree;
Node(){
lc = rc = nullptr;
tree = segTree1d();
}
~Node(){
if(lc) delete lc;
if(rc) delete rc;
}
void update(int l, int r, int x, int y, ll v){
if(l==r){
tree.update(y, v);
return;
}
int m = (l+r)>>1;
if(x<=m){
if(!lc) lc = new Node();
lc->update(l, m, x, y, v);
tree.update(y, __gcd(lc->tree.query(y, y), rc ? rc->tree.query(y, y) : 0));
}
else{
if(!rc) rc = new Node();
rc->update(m+1, r, x, y, v);
tree.update(y, __gcd(rc->tree.query(y, y), lc ? lc->tree.query(y, y) : 0));
}
}
ll query(int l, int r, int s, int e, int ys, int ye){
if(r<s || e<l) return 0;
if(s<=l && r<=e) return tree.query(ys, ye);
int m = (l+r)>>1;
return __gcd(lc ? lc->query(l, m, s, e, ys, ye) : 0, rc ? rc->query(m+1, r, s, e, ys, ye) : 0);
}
} *root;
segTree2d(){
root = new Node();
}
void update(int x, int y, ll v){
root->update(0, n-1, x, y, v);
}
ll query(int xs, int xe, int ys, int ye){
return root->query(0, n-1, xs, xe, ys, ye);
}
} tree;
void init(int R, int C){
n = R, m = C;
}
void update(int P, int Q, ll K) {
tree.update(P, Q, K);
}
ll calculate(int P, int Q, int U, int V){
return tree.query(P, U, Q, V);
}
