#include "game.h"
#include <bits/stdc++.h>
#define CNT (int)2e7
#define CNT2 (int)1e6
using namespace std;
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[CNT];
int cnt = 1;
struct SegTree{
int root = -1;
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,1e9,pos,val);
}
long long get(int l,int r){
if(root == -1)
return 0;
return get(root,1,1e9,l,r);
}
};
map<int,int> mp;
int cntmp = 1;
SegTree numbers[22005];
struct node2{
int l = 0,r = 0;
SegTree val;
}nodes2[CNT2];
int cnt2 = 1;
struct SegTree2D{
int root = -1;
void upd(int v,int tl,int tr,int x,int y,long long val){
nodes2[v].val.upd(y,numbers[mp[y]].get(tl,tr));
if(tl == tr){
return;
}
int tm = (tl + tr)/2;
if(x <= tm){
if(nodes2[v].l == 0)
nodes2[v].l = cnt2++;
upd(nodes2[v].l,tl,tm,x,y,val);
}
else{
if(nodes2[v].r == 0)
nodes2[v].r = cnt2++;
upd(nodes2[v].r,tm+1,tr,x,y,val);
}
}
long long get(int v,int tl,int tr,int l,int r,int l2,int r2){
if(v == 0 || tr < l || r < tl)
return 0;
if(l <= tl && tr <= r){
return nodes2[v].val.get(l2,r2);
}
int tm = (tl + tr)/2;
return gcd2(get(nodes2[v].l,tl,tm,l,r,l2,r2),get(nodes2[v].r,tm+1,tr,l,r,l2,r2));
}
void upd(int x,int y,long long val){
if(root == -1)
root = cnt2++;
upd(root,1,1e9,x,y,val);
}
long long get(int l,int r,int l2,int r2){
if(root == -1)
root = cnt2++;
return get(root,1,1e9,l,r,l2,r2);
}
}tree;
vector<pair<pair<int,int>,long long>>points;
void init(int R, int C) {
//tree.init(R,C);
}
int update_cnt = 0;
void update(int P, int Q, long long K) {
P++,Q++;
update_cnt++;
bool ok = 1;
for(auto u:points){
if(u.first == make_pair(P,Q)){
u.second = K;
ok = 0;
}
}
if(ok){
points.push_back({{P,Q},K});
}
if(update_cnt <= 1.5e4){
if(mp[Q] == 0){
mp[Q] = cntmp++;
}
numbers[mp[Q]].upd(P,K);
tree.upd(P,Q,K);
}
}
long long calculate(int P, int Q, int U, int V) {
P++,Q++,U++,V++;
assert(cnt < CNT);
assert(cnt2 < CNT2);
if(update_cnt <= 1.5e4)
return tree.get(P,U,Q,V);
long long g = 0;
for(auto u:points){
if(P <= u.first.first && u.first.first <= U && Q <= u.first.second && u.first.second <= V){
g = gcd2(g,u.second);
}
}
return g;
}
