#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const int N = 1e9 + 7;
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;
}
int get_midpoint(int l, int r) {//[l, r)
int pow_2 = 1 << __lg(r-l);//bit_floor(unsigned(r-l));
return min(l + pow_2, r - pow_2/2);
}
struct SEGT{
struct Node{
int left , right;
long long value;
Node():left(-1),right(-1),value(0){}
};
vector < Node > tree;
SEGT(){
tree.push_back(Node());
}
long long query(int ql , int qr , int ind=0 , int l=0 , int r=N){
if(l >= ql and r <= qr)return tree[ind].value;
else if(l > qr or r < ql)return 0;
int mid = get_midpoint(l,r);
long long resleft = tree[ind].left == -1 ? 0 : query(ql,qr,tree[ind].left,l,mid);
long long resright = tree[ind].right == -1 ? 0 : query(ql,qr,tree[ind].right,mid+1,r);
return gcd2(resleft , resright);
}
void update(int qp , long long qv , int ind=0 , int l=0 , int r=N){
if(l == r){
tree[ind].value = qv;
return;
}
int mid = get_midpoint(l,r);
if(qp <= mid){
if(tree[ind].left == -1){
tree[ind].left = sz(tree);
tree.push_back(Node());
}
update(qp,qv,tree[ind].left,l,mid);
}
else{
if(tree[ind].right == -1){
tree[ind].right = sz(tree);
tree.push_back(Node());
}
update(qp,qv,tree[ind].right,mid+1,r);
}
long long resleft = tree[ind].left == -1 ? 0 : tree[tree[ind].left].value;
long long resright = tree[ind].right == -1 ? 0 : tree[tree[ind].right].value;
tree[ind].value = gcd2(resleft , resright);
}
};
struct SEGT2D{
struct Node{
int left , right;
SEGT value;
Node():left(-1),right(-1){}
};
vector < Node > tree;
SEGT2D(){
tree.push_back(Node());
}
long long query(int ql , int qr , int ql2 , int qr2 , int ind=0 , int l=0 , int r=N){
if(l >= ql and r <= qr)return tree[ind].value.query(ql2,qr2);
else if(l > qr or r < ql)return 0;
int mid = get_midpoint(l,r);
long long resleft = tree[ind].left == -1 ? 0 : query(ql,qr,ql2,qr2,tree[ind].left,l,mid);
long long resright = tree[ind].right == -1 ? 0 : query(ql,qr,ql2,qr2,tree[ind].right,mid+1,r);
return gcd2(resleft , resright);
}
void update(int qp , int qp2 , long long qv , int ind=0 , int l=0 , int r=N){
if(l == r){
tree[ind].value.update(qp2,qv);
return;
}
int mid = get_midpoint(l,r);
if(qp <= mid){
if(tree[ind].left == -1){
tree[ind].left = sz(tree);
tree.push_back(Node());
}
update(qp,qp2,qv,tree[ind].left,l,mid);
}
else{
if(tree[ind].right == -1){
tree[ind].right = sz(tree);
tree.push_back(Node());
}
update(qp,qp2,qv,tree[ind].right,mid+1,r);
}
long long resleft = tree[ind].left == -1 ? 0 : tree[tree[ind].left].value.query(qp2,qp2);
long long resright = tree[ind].right == -1 ? 0 : tree[tree[ind].right].value.query(qp2,qp2);
tree[ind].value.update(qp2 , gcd2(resleft , resright));
}
} segt;
void init(int R, int C) {
37;
}
void update(int P, int Q, long long K) {
segt.update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return segt.query(min(P,U),max(P,U),min(Q,V),max(Q,V));
}
