#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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 SegTree{
vector<long long> t;
int n;
SegTree(int size){
n = size;
t.assign(4*n,0);
}
void init(int size){
n = size;
t.assign(4*n,0);
}
void upd(int v,int tl,int tr,int pos,long long val){
if(tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm)
upd(v*2,tl,tm,pos,val);
else upd(v*2+1,tm+1,tr,pos,val);
t[v] = __gcd(t[v*2],t[v*2+1]);
}
long long get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl)
return 0;
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr)/2;
return __gcd(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd(int pos,long long val){
upd(1,1,n,pos,val);
}
long long get(int l,int r){
return get(1,1,n,l,r);
}
};
struct SegTree2D{
vector<SegTree> t;
int n;
void init(int size1,int size2){
n = size1;
t.assign(4*n,size2);
}
void upd(int v,int tl,int tr,int x,int y,long long val){
t[v].upd(y,val);
if(tl == tr){
return;
}
int tm = (tl + tr)/2;
if(x <= tm)
upd(v*2,tl,tm,x,y,val);
else upd(v*2+1,tm+1,tr,x,y,val);
}
long long get(int v,int tl,int tr,int l,int r,int l2,int r2){
if(tr < l || r < tl)
return 0;
if(l <= tl && tr <= r){
return t[v].get(l2,r2);
}
int tm = (tl + tr)/2;
return __gcd(get(v*2,tl,tm,l,r,l2,r2),get(v*2+1,tm+1,tr,l,r,l2,r2));
}
void upd(int x,int y,long long val){
upd(1,1,n,x,y,val);
}
long long get(int l,int r,int l2,int r2){
return get(1,1,n,l,r,l2,r2);
}
}tree;
void init(int R, int C) {
tree.init(R,C);
}
void update(int P, int Q, long long K) {
P++,Q++;
tree.upd(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
P++,Q++,U++,V++;
return tree.get(P,U,Q,V);
}
