#include<bits/stdc++.h>
#define pb push_back
#include "game.h"
using namespace std;
const int N = 1e9;
const int L = 0;
long long lval, rval;
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{
node *lc, *rc;
long long gcd;
node(){
gcd = 0;
lc = rc = nullptr;
}
};
struct node1{
node1 *lc, *rc;
node *in;
node1(){
lc = rc = nullptr;
in = nullptr;
}
};
node1 *kok;
long long queryY(node *root, int l, int r, int &ql, int &qr){
if(l > r || ql > qr || l > qr || r < ql) return 0;
if(l >= ql && r <= qr){
return root->gcd;
}
else{
int m = (l + r)/2;
return gcd2((root->lc == nullptr ? 0LL: queryY(root->lc, l, m, ql, qr)), (root->rc == nullptr ? 0LL: queryY(root->rc, m+1, r, ql, qr)));
}
}
long long queryX(node1 *root, int l, int r, int &ql, int &qr, int &qly, int &qry){
if(l > r || ql > qr || l > qr || r < ql) return 0;
if(l >= ql && r <= qr){
if(root->in == nullptr) return 0;
else return queryY(root->in, L, N, qly, qry);
}
else{
int m = (l + r)/2;
return gcd2((root->lc == nullptr ? 0LL: queryX(root->lc, l, m, ql, qr, qly, qry)) , (root->rc == nullptr ? 0LL: queryX(root->rc, m+1, r, ql, qr, qly, qry)));
}
}
void updateY(node *root, int l, int r, int &y, long long val){
if(l == r){
root->gcd = val;
}
else{
int m = (l + r)/2;
if(y <= m){
if(root->lc == nullptr){
root->lc = new node();
}
updateY(root->lc, l, m, y, val);
}
else{
if(root->rc == nullptr){
root->rc = new node();
}
updateY(root->rc, m+1, r, y, val);
}
root->gcd = gcd2((root->lc == nullptr ? 0 : root->lc->gcd), (root->rc == nullptr ? 0 : root->rc->gcd));
}
}
void updateX(node1 *root, int l, int r, int &x, int &y, long long val){
if(l == r){
if(root->in == nullptr){
root->in = new node();
}
updateY(root->in, L, N, y, val);
}
else{
int m = (l + r)/2;
if(x <= m){
if(root->lc == nullptr){
root->lc = new node1();
}
updateX(root->lc, l, m, x, y, val);
}
else{
if(root->rc == nullptr){
root->rc = new node1();
}
updateX(root->rc, m+1, r, x, y, val);
}
if(root->in == nullptr){
root->in = new node();
}
lval = 0, rval = 0;
if(root->lc != nullptr && root->lc->in != nullptr) lval = queryY(root->lc->in, L, N, y, y);
if(root->rc != nullptr && root->rc->in != nullptr) rval = queryY(root->rc->in, L, N, y, y);
updateY(root->in, L, N, y, gcd2(lval, rval));
}
}
void init(int R, int C) {
kok = new node1();
}
void update(int P, int Q, long long K){
updateX(kok, L, N, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryX(kok, L, N, P, U, Q, V);
}
