#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define f first
#define s second
ll gcd(ll a, ll b){
if (a == 0) return b;
return gcd(b%a,a);
}
using sn = struct node*;
const int low = 0;
const int high = 1e9;
struct node {
int l,r;
bool w;
ll val = 0;
sn c[2] = {nullptr,nullptr};
sn root = nullptr;
node(int il, int ir, bool iw){
l = il;
r = ir;
w = iw;
}
};
void upd(sn cur, int x, int y, ll v, bool rep = 0){
int l = (*cur).l;
int r = (*cur).r;
if ((*cur).w){
//cout << l << "," << r << "\n";
//y
if (l == r && rep) { (*cur).val = v; return;}
(*cur).val = gcd((*cur).val, v);
if (l == r) return;
int m = (l+r)/2;
if (y <= m) {
if ((*cur).c[0] == nullptr) (*cur).c[0] = new node(l,m,1);
upd((*cur).c[0],x,y,v);
} else {
if ((*cur).c[1] == nullptr) (*cur).c[1] = new node(m+1,r,1);
upd((*cur).c[1],x,y,v);
}
} else {
//x
if ((*cur).root == nullptr) (*cur).root = new node(low,high,1);
upd((*cur).root,x,y,v,(l==r));
//cout << l << ',' << r << " " << x << "-" << y << "\n";
if (l == r) return;
int m = (l+r)/2;
if (x <= m) {
if ((*cur).c[0] == nullptr) (*cur).c[0] = new node(l,m,0);
upd((*cur).c[0],x,y,v);
} else {
if ((*cur).c[1] == nullptr) (*cur).c[1] = new node(m+1,r,0);
upd((*cur).c[1],x,y,v);
}
}
}
ll query(sn cur, int x1, int x2, int y1, int y2){
int l = (*cur).l;
int r = (*cur).r;
//cout << "Q - " << l << ',' << r << " " << (*cur).w << ' ' << (*cur).val << '\n';
//cout << x1 << ',' << x2 << " " << y1 << ',' << y2 << '\n';
if ((*cur).w){
//y
ll res = 0;
//cout << "CONTINUING\n";
if (l >= y1 && r <= y2) return (*cur).val;
//cout << "CONTINUING\n";
if (l > y2 || r < y1) return 0;
if ((*cur).c[0] != nullptr) res = gcd(res,query((*cur).c[0],x1,x2,y1,y2));
if ((*cur).c[1] != nullptr) res = gcd(res,query((*cur).c[1],x1,x2,y1,y2));
return res;
} else {
//x
ll res = 0;
if (l >= x1 && r <= x2){
if ((*cur).root != nullptr) res = query((*cur).root,x1,x2,y1,y2);
return res;
}
if (l > x2 || r < x1) return 0;
if ((*cur).c[0] != nullptr) res = gcd(res,query((*cur).c[0],x1,x2,y1,y2));
if ((*cur).c[1] != nullptr) res = gcd(res,query((*cur).c[1],x1,x2,y1,y2));
return res;
}
}
sn groot = nullptr;
void init(int R, int C){
groot = new node(low,high,0);
}
void update(int P, int Q, ll K){
upd(groot,Q,P,K);
}
ll calculate(int P, int Q, int U, int V){
return query(groot,Q,V,P,U);
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int r,c,n;
cin >> r >> c >> n;
init(r,c);
int t,u,v,a,b;
//cout << calculate(0,0,10,10) << '\n';
for (int i = 0; i < n; i++){
cin >> t;
if (t == 1){
cin >> u >> v >> a;
update(u,v,a);
//cout << calculate(0,0,10,10) << '\n';
} else {
cin >> u >> v >> a >> b;
cout << calculate(u,v,a,b) << '\n';
}
}
return 0;
}
*/
