#include <bits/stdc++.h>
#include "game.h"
#define ll long long
using namespace std;
#define ff first
#define ss second
int n,m;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct node
{
node *l, *r;
ll val;
node()
{
l=r=0;
val=0;
}
};
struct node2
{
node2 *l, *r;
node *it;
node2()
{
l=r=0;
it=0;
}
};
node2 *tree;
ll get_val(node *&x)
{
return (x)?x->val:0LL;
}
ll get(node *&u, int ly, int ry, int l, int r)
{
if (!u) return 0LL;
if (ly>r||ry<l) return 0LL;
if (ly>=l&&ry<=r) return u->val;
int mid=(ly+ry)/2;
return gcd2(get(u->l,ly,mid,l,r),get(u->r,mid+1,ry,l,r));
}
ll get2(node2 *&u, int lx, int rx, int l, int r, int ly, int ry)
{
if (!u) return 0LL;
if (lx>r||rx<l) return 0LL;
if (lx>=l&&rx<=r) return get(u->it,1,m,ly,ry);
int mid=(lx+rx)/2;
return gcd2(get2(u->l,lx,mid,l,r,ly,ry),get2(u->r,mid+1,rx,l,r,ly,ry));
}
void upd(node *&u, int ly, int ry, int idx, int idy, ll val)
{
if (!u) u=new node();
if (ly==ry)
{
u->val=val;
return;
}
int mid=(ly+ry)/2;
if (idy<=mid)
upd(u->l,ly,mid,idx,idy,val);
else
upd(u->r,mid+1,ry,idx,idy,val);
u->val = gcd2(get_val(u->l),get_val(u->r));
}
void upd2(node2 *&u, int lx, int rx, int idx, int idy, ll val)
{
if (!u) u=new node2();
if (lx==rx)
{
upd(u->it,1,m,idx,idy,val);
return;
}
int mid=(lx+rx)/2;
if (idx<=mid)
upd2(u->l,lx,mid,idx,idy,val);
else
upd2(u->r,mid+1,rx,idx,idy,val);
ll L=0LL, R=0LL;
if (u->l) L=get(u->l->it,1,m,idy,idy);
if (u->r) R=get(u->r->it,1,m,idy,idy);
val=gcd2(L,R);
upd(u->it,1,m,idx,idy,val);
}
void init(int R, int C) {
n=R; m=C;
}
void update(int P, int Q, long long K) {
P++; Q++; upd2(tree,1,n,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
P++; Q++; U++; V++;
return get2(tree,1,n,P,U,Q,V);
}
