#include "game.h"
#include <bits/stdc++.h>
#define N 4000005
using namespace std;
int R,C;
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{
int l = 0,r = 0;
long long val = 0;
}nodes[N];
int cnt = 1;
struct SegTree{
int root = -1;
int n = 1e9;
void upd(int v,int tl,int tr,int pos,long long val){
if(tl == tr){
nodes[v].val = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm){
if(nodes[v].l == 0)
nodes[v].l = cnt++;
upd(nodes[v].l,tl,tm,pos,val);
}
else{
if(nodes[v].r == 0)
nodes[v].r = cnt++;
upd(nodes[v].r,tm+1,tr,pos,val);
}
nodes[v].val = gcd2(nodes[nodes[v].l].val,nodes[nodes[v].r].val);
}
long long get(int v,int tl,int tr,int l,int r){
if(v == 0 || tr < l || r < tl)
return 0;
if(l <= tl && tr <= r){
return nodes[v].val;
}
int tm = (tl + tr)/2;
return gcd2(get(nodes[v].l,tl,tm,l,r),get(nodes[v].r,tm+1,tr,l,r));
}
void upd(int pos,long long val){
if(root == -1)
root = cnt++;
upd(root,1,n,pos,val);
}
long long get(int l,int r){
if(root == -1)
root = cnt++;
return get(root,1,n,l,r);
}
};
struct Node2{
int lc,rc;
SegTree t;
Node2():lc(0),rc(0){
}
}t2[N];
int cnt2 = 1;
map<int,SegTree> mp;
struct SegTree2D{
int root;
SegTree2D():root(0){}
void upd(int v,int tl,int tr,int pos1,int pos2){
t2[v].t.upd(pos2,mp[pos2].get(tl,tr));
if(tl == tr){
return;
}
int tm = (tl + tr)/2;
if(pos1 <= tm){
if(t2[v].lc == 0)
t2[v].lc = cnt2++;
upd(t2[v].lc,tl,tm,pos1,pos2);
}
else{
if(t2[v].rc == 0)
t2[v].rc = cnt2++;
upd(t2[v].rc,tm+1,tr,pos1,pos2);
}
}
long long get(int v,int tl,int tr,int l1,int r1,int l2,int r2){
//cout << v << ' ' << tl << ' ' << tr << endl;
if(v == 0 || tr < l1 || r1 < tl){
return 0;
}
if(l1 <= tl && tr <= r1){
return t2[v].t.get(l2,r2);
}
int tm = (tl + tr)/2;
return __gcd(get(t2[v].lc,tl,tm,l1,r1,l2,r2),get(t2[v].rc,tm+1,tr,l1,r1,l2,r2));
}
void upd(int pos1,int pos2){
if(root == 0){
root = cnt2++;
}
upd(root,0,R-1,pos1,pos2);
}
long long get(int l1,int r1,int l2,int r2){
return get(root, 0, R-1, l1, r1, l2, r2);
}
}tree;
void init(int r, int c) {
R = r;
C = c;
}
void update(int P, int Q, long long K) {
mp[Q].upd(P,K);
tree.upd(P,Q);
}
long long calculate(int P, int Q, int U, int V) {
return tree.get(P,U,Q,V);
}
