#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<30);
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{
ll val=0;
node* l=nullptr, *r=nullptr;
node(ll _val): val(_val){}
};
ll val(node* v){
if(!v)return 0;
return v->val;
}
void upd(node* v){
if(!v)return;
v->val=gcd2(val(v->l), val(v->r));
}
ll quer1d(node* v, int L, int R, int l, int r){
if(!v)return 0;
//cout<<L<<" "<<R<<" "<<v->val<<"q\n";
if(l==L && r==R){
return v->val;
}
int M=(L+R)>>1;
ll ans=0;
if(l<=M)ans=gcd2(ans, quer1d(v->l, L, M, l, min(M, r)));
if(r>M)ans=gcd2(ans, quer1d(v->r, M+1, R, max(l, M+1), r));
return ans;
}
node* upd1d(node* v, int L, int R, int i, ll val){
if(!v)v=new node(0);
if(L==R){
//cout<<v->val<<" "<<val<<" "<<i<<"u\n";
v->val=val;
return v;
}
//cout<<L<<" "<<R<<" "<<v->val<<"a\n";
int M=(L+R)>>1;
if(i<=M)v->l=upd1d(v->l, L, M, i, val);
else v->r=upd1d(v->r, M+1, R, i, val);
upd(v);
//cout<<L<<" "<<R<<" "<<v->val<<"b\n";
return v;
}
struct node2{
node* val=nullptr;
node2* l=nullptr, *r=nullptr;
node2(node* _v): val(_v){}
};
ll quer2d(node2* v, int L, int R, int l, int r, int x, int y){
if(!v)return 0;
if(l==L && r==R){
return quer1d(v->val, 0, N-1, x, y);
}
int M=(L+R)>>1;
ll ans=0;
if(l<=M)ans=gcd2(ans, quer2d(v->l, L, M, l, min(M, r), x, y));
if(r>M)ans=gcd2(ans, quer2d(v->r, M+1, R, max(l, M+1), r, x, y));
return ans;
}
node* Val(node2* v){
if(!v)return 0;
return v->val;
}
node2* upd2d(node2* v, int L, int R, int i, int j, ll val){
if(!v)v=new node2(nullptr);
if(L==R){
v->val=upd1d(v->val, 0, N-1, j, val);
return v;
}
int M=(L+R)>>1;
if(i<=M)v->l=upd2d(v->l, L, M, i, j, val);
else v->r=upd2d(v->r, M+1, R, i, j, val);
v->val=upd1d(v->val, 0, N-1, j, gcd2(quer1d(Val(v->l), 0, N-1, j, j), quer1d(Val(v->r), 0, N-1, j, j)));
return v;
}
node2* root=nullptr;
void init(int R, int C) {
/* ... */
}
void update(int P, int Q, long long K) {
root=upd2d(root, 0, N-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return quer2d(root, 0, N-1, P, U, Q, V);
}
