#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int c, rl;
ll gcd(ll x,ll y){
if(x == 0 or y == 0) return max(x,y);
return __gcd(x,y);
}
struct Node{
Node* lS;
Node* rS;
int l, r, m;
ll val;
ll tmp_val;
Node(){
val = 0;
lS = nullptr;
rS = nullptr;
l = 0;
r = 0;
m = 0;
}
Node(int l1,int r1){
val = 0;
lS = nullptr;
rS = nullptr;
l = l1;
r = r1;
m = (l+r)/2;
}
ll get(int tl,int tr){
if(tl <= l and r <= tr) return val;
if(tr <= m){
if(lS) return lS->get(tl,tr);
return 0;
}
else if(tl > m){
if(rS) return rS->get(tl,tr);
return 0;
}else{
tmp_val = 0;
if(lS) tmp_val = lS->get(tl,m);
if(rS) tmp_val = gcd(tmp_val,(rS->get(m,tr)));
return tmp_val;
}
}
void update(int y,ll vals){
if(l == r) {
val = vals;
return;
}
if(y <= m){
if(!lS) lS = new Node(l,m);
lS->update(y,vals);
}
if(y > m){
if(!rS) rS = new Node(m+1,r);
rS->update(y,vals);
}
val = 0;
if(lS) val = lS->val;
if(rS) val = gcd(val,rS->val);
}
};
struct Node2{
Node2 *lS;
Node2 *rS;
Node *root;
int l,r,m;
ll tmp_val;
Node2(){
lS = nullptr;
rS = nullptr;
l = r = 0;
root = new Node(0,c);
}
Node2(int l1,int r1){
lS = nullptr;
rS = nullptr;
l = l1;
r = r1;
m = (l+r)/2;
root = new Node(0,c);
}
ll get(int x1,int x2,int y1,int y2){
if(x1 <= l and r <= x2) return root->get(y1,y2);
if(x2 <= m){
if(lS) return lS->get(x1,x2,y1,y2);
return 0;
}
else if(x1 > m){
if(rS) return rS->get(x1,x2,y1,y2);
return 0;
}else{
tmp_val = 0;
if(lS) tmp_val = lS->get(x1,m,y1,y2);
if(rS) tmp_val = gcd(tmp_val,(rS->get(m+1,x2,y1,y2)));
return tmp_val;
}
}
void update(int x,int y,ll vals){
if(l == r){
root->update(y,vals);
return;
}
if(x <= m){
if(!lS) lS = new Node2(l,m);
lS->update(x,y,vals);
}
if(x > m){
if(!rS) rS = new Node2(m+1,r);
rS->update(x,y,vals);
}
tmp_val = 0;
if(lS) tmp_val = lS->root->get(y,y);
if(rS) tmp_val = gcd(tmp_val,rS->root->get(y,y));
root->update(y,tmp_val);
}
};
Node2 *root = nullptr;
void init(int R,int C){
rl = R-1;
c = C-1;
root = new Node2(0,rl);
}
void update(int P,int Q,ll K){
root->update(P,Q,K);
}
ll calculate(int P,int Q,int U,int V){
return root->get(P,U,Q,V);
}
/*
int main(){
int t1,t2,t3;
cin >> t1 >> t2 >> t3;
init(t1,t2);
while (t3--){
int type;
cin >> type;
if(type == 1){
int x,y;
ll val;
cin >> x >> y >> val;
update(x,y,val);
}
if(type == 2){
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << calculate(x1,y1,x2,y2) << "\n";
}
}
return 0;
}*/
