#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct Seg
{
int l, r;
long long v;
Seg() : l(0), r(0), v(0) {}
};
const int MAX=1e9;
vector<Seg> tree(2), tree2(1);
long long GCD(long long a, long long b)
{
for(;b;a%=b,swap(a,b));
return a;
}
long long get_gcd2(int n1, int n2, int p, int s=0, int e=MAX)
{
int m=(s+e)>>1;
if(p==0 || n2<s || e<n1) return 0;
if(tree2[p].l<0) return n1<=-tree2[p].l-1 && -tree2[p].l-1<=n2 ? tree2[p].v:0;
if(n1<=s && e<=n2) return tree2[p].v;
return GCD(get_gcd2(n1,n2,tree2[p].l,s,m),get_gcd2(n1,n2,tree2[p].r,m+1,e));
}
long long get_gcd(int x1, int x2, int y1, int y2, int p=1, int s=0, int e=MAX)
{
int m=(s+e)>>1;
if(p==0 || x2<s || e<x1) return 0;
if(x1<=s && e<=x2) return get_gcd2(y1,y2,tree[p].v);
return GCD(get_gcd(x1,x2,y1,y2,tree[p].l,s,m),get_gcd(x1,x2,y1,y2,tree[p].r,m+1,e));
}
void set_tree2(int n, long long v, int p, int s=0, int e=MAX)
{
int m=(s+e)>>1;
if(s==e) {
tree2[p].v=v;
return;
}
if(tree2[p].l<0) {
int t=-tree2[p].l-1;
if(t==n) {
tree2[p].v=v;
return;
}
tree2[p].l=0;
if(t<=m) {
tree2[p].l=tree2.size(), tree2.push_back(Seg());
tree2[tree2[p].l].l=-t-1;
tree2[tree2[p].l].v=tree2[p].v;
}
else {
tree2[p].r=tree2.size(), tree2.push_back(Seg());
tree2[tree2[p].r].l=-t-1;
tree2[tree2[p].r].v=tree2[p].v;
}
}
if(tree2[p].l==0 && tree2[p].r==0) {
tree2[p].v=v;
tree2[p].l=-n-1;
return;
}
if(n<=m) {
if(tree2[p].l==0) tree2[p].l=tree2.size(), tree2.push_back(Seg());
set_tree2(n,v,tree2[p].l,s,m);
}
else {
if(tree2[p].r==0) tree2[p].r=tree2.size(), tree2.push_back(Seg());
set_tree2(n,v,tree2[p].r,m+1,e);
}
tree2[p].v=GCD(tree2[tree2[p].l].v,tree2[tree2[p].r].v);
}
void set_tree(int x, int y, long long v, int p=1, int s=0, int e=MAX)
{
int m=(s+e)>>1;
if(tree[p].v==0) tree[p].v=tree2.size(), tree2.push_back(Seg());
if(s==e) {
set_tree2(y,v,tree[p].v);
return;
}
if(x<=m) {
if(tree[p].l==0) tree[p].l=tree.size(), tree.push_back(Seg());
set_tree(x,y,v,tree[p].l,s,m);
}
else {
if(tree[p].r==0) tree[p].r=tree.size(), tree.push_back(Seg());
set_tree(x,y,v,tree[p].r,m+1,e);
}
set_tree2(y,GCD(get_gcd2(y,y,tree[tree[p].l].v),get_gcd2(y,y,tree[tree[p].r].v)),tree[p].v);
}
void init(int R, int C) {}
void update(int P, int Q, long long K) {set_tree(P,Q,K);}
long long calculate(int P, int Q, int U, int V) {return get_gcd(P,U,Q,V);}
