#include "bits/stdc++.h"
#include "game.h"
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 N , M;
struct NODE{
NODE *l , *r;
long long G = 0;
};
struct node{
node *l , *r;
NODE *v;
} *root;
void init(int R, int C) {
N = R;
M = C;
}
void upd(NODE *&u , int l , int r , int p , long long x){
if(!u){
u = new NODE();
}
if(l == r){
u->G = x;
return;
}
int m = (l + r) / 2;
if(p <= m){
upd(u->l , l , m , p , x);
}else{
upd(u->r , m + 1 , r , p , x);
}
if(!u->l){
u->l = new NODE();
}
if(!u->r){
u->r = new NODE();
}
u->G = gcd2(u->l->G , u->r->G);
};
void update(node* &u , int l , int r , int p , int q , long long x){
if(l > r){
return;
}
if(!u){
u = new node();
}
upd(u->v , 1 , M , q , x);
if(l == r){
return;
}
int m = (l + r) / 2;
if(p <= m){
update(u->l , l , m , p , q , x);
}else{
update(u->r , m + 1 , r , p , q , x);
}
}
void update(int P, int Q, long long K) {
++P , ++Q;
update(root , 1 , N , P , Q , K);
}
long long query(NODE *&u , int l , int r , int L , int R){
if(l > r || r < L || l > R || !u){
return 0LL;
}
if(L <= l && r <= R){
return u->G;
}
int m = (l + r) / 2;
return gcd2(query(u->l , l , m , L , R) , query(u->r , m + 1 , r , L , R));
}
long long query(node*&u , int l , int r , int L , int R, int LL , int RR){
if(l > r || r < L || l > R || !u){
return 0LL;
}
if(L <= l && r <= R){
return query(u->v , 1 , M , LL , RR);
}
int m = (l + r) / 2;
return gcd2(query(u->l , l , m , L , R , LL , RR) , query(u->r , m + 1 , r , L , R , LL , RR));
};
long long calculate(int P, int Q, int U, int V) {
++P , ++Q , ++U , ++V;
swap(Q , U);
return query(root , 1 , N , P , Q , U , V);
}
