#include <bits/stdc++.h>
#include "game.h"
#define ll long long
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int inf = 1e9 + 7;
int n,m;
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 *l=nullptr, *r=nullptr;
int wt; ll val=0LL, vval=0LL;
ii key;
node (ii _key, ll x)
{
key=_key; val=x;
vval=x;
wt=rng()%INT_MAX;
}
};
struct Node
{
Node *l=nullptr, *r=nullptr;
node *it=nullptr;
Node() {}
};
Node *tree = nullptr;
inline ll get_g(node *&x)
{
return (x)?x->val:0LL;
}
void upd(node *&x)
{
if (!x) return;
x->val = gcd2(x->vval,gcd2(get_g(x->l),get_g(x->r)));
}
pair<node*, node*> split(node *x, ii key)
{
if (!x) return {nullptr,nullptr};
if (x->key<=key) {pair<node*,node*> tt=split(x->r,key); x->r=tt.ff; upd(x); return{x,tt.ss}; }
else {pair<node*,node*> tt=split(x->l,key); x->l=tt.ss; upd(x); return {tt.ff,x}; }
}
node* merg(node *l, node *r)
{
if (!l||!r) return (!l)?r:l;
if (l->wt>r->wt){
l->r=merg(l->r,r); upd(l); return l;
}
else {
r->l=merg(l,r->l); upd(r); return r;
}
}
void ins(node *&x, ii key, ll val)
{
// cout<<key.ff<<' '<<key.ss<<" = "<<val<<'\n';
auto [a,b] = split(x,make_pair(key.ff,key.ss-1));
auto [c,d] = split(b,key);
x = merg(merg(a,(new node(key,val))),d);
}
ll get2(node *&x, int l, int r)
{
auto [a,b] = split(x,make_pair(l-1,inf));
auto [c,d] = split(b,make_pair(r,inf));
ll ans = get_g(c);
// cout<<ans<<'\n';
x = merg(a,merg(c,d));
return ans;
}
void updat(Node *&x, int lx, int rx, int idx, int idy, ll val)
{
if (!x) x=new Node();
// cout<<lx<<' '<<rx<<" + ";
ins(x->it,{idy,idx},val);
if (lx==rx) return;
int mid=(lx+rx)/2;
if (idx<=mid) updat(x->l,lx,mid,idx,idy,val);
else updat(x->r,mid+1,rx,idx,idy,val);
}
ll get(Node *x, int lx, int rx, int l, int r, int ly, int ry)
{
if (!x) return 0LL;
if (lx>r||rx<l) return 0LL;
if (lx>=l&&rx<=r)
{
// cout<<l<<' '<<r<<' '<<ly<<' '<<ry<<": ";
return get2(x->it,ly,ry);
}
int mid=(lx+rx)/2;
return gcd2(get(x->l,lx,mid,l,r,ly,ry),get(x->r,mid+1,rx,l,r,ly,ry));
}
void init(int R, int C) {
n=R; m=C;
}
void update(int P, int Q, long long K) {
P++; Q++;
updat(tree,1,n,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
P++; Q++; U++; V++;
return get(tree,1,n,P,U,Q,V);
}
