#include "game.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node2
{
node2 *lc, *rc;
ll l, r, val;
node2(ll l, ll r) : lc(0), rc(0), l(l), r(r), val(0) {}
};
struct node1
{
node1 *lc, *rc;
node2 *x;
ll l, r;
node1(ll l, ll r) : lc(0), rc(0), x(0), l(l), r(r) {}
} root(0, 1e9);
void upd2(node2 *i, ll y, ll z)
{
if (i->l==i->r)
{
i->val=z;
return;
}
ll mid=(i->l+i->r)/2;
if (y<=mid)
{
if (!i->lc)
i->lc=new node2(y, y);
else if (y<i->lc->l || i->lc->r<y)
{
ll l=i->l, r=mid, m=(l+r)/2;
while ((y<=m)^(i->lc->l>m))
{
if (y<=m)
r=m;
else
l=m+1;
m=(l+r)/2;
}
node2 *j=new node2(l, r);
if (i->lc->l<=m)
j->lc=i->lc;
else
j->rc=i->lc;
i->lc=j;
}
upd2(i->lc, y, z);
}
else
{
if (!i->rc)
i->rc=new node2(y, y);
else if (y<i->rc->l || i->rc->r<y)
{
ll l=mid+1, r=i->r, m=(l+r)/2;
while ((y<=m)^(i->rc->l>m))
{
if (y<=m)
r=m;
else
l=m+1;
m=(l+r)/2;
}
node2 *j=new node2(l, r);
if (i->rc->l<=m)
j->lc=i->rc;
else
j->rc=i->rc;
i->rc=j;
}
upd2(i->rc, y, z);
}
i->val=gcd(i->lc?i->lc->val:0, i->rc?i->rc->val:0);
}
ll qry2(node2 *i, ll ql, ll qr)
{
if (ql<=i->l && i->r<=qr)
return i->val;
ll res=0;
if (i->lc && i->lc->l<=qr && ql<=i->lc->r)
res=gcd(res, qry2(i->lc, ql, qr));
if (i->rc && i->rc->l<=qr && ql<=i->rc->r)
res=gcd(res, qry2(i->rc, ql, qr));
return res;
}
void upd1(node1 *i, ll x, ll y, ll z)
{
if (i->l==i->r)
{
if (!i->x)
i->x=new node2(0, 1e9);
upd2(i->x, y, z);
return;
}
ll mid=(i->l+i->r)/2;
if (x<=mid)
{
if (!i->lc)
i->lc=new node1(i->l, mid);
upd1(i->lc, x, y, z);
}
else
{
if (!i->rc)
i->rc=new node1(mid+1, i->r);
upd1(i->rc, x, y, z);
}
if (!i->x)
i->x=new node2(0, 1e9);
upd2(i->x, y, gcd(i->lc?qry2(i->lc->x, y, y):0, i->rc?qry2(i->rc->x, y, y):0));
}
ll qry1(node1 *i, ll ql1, ll qr1, ll ql2, ll qr2)
{
if (ql1<=i->l && i->r<=qr1)
return qry2(i->x, ql2, qr2);
ll mid=(i->l+i->r)/2, res=0;
if (i->l<=qr1 && ql1<=mid && i->lc)
res=gcd(res, qry1(i->lc, ql1, qr1, ql2, qr2));
if (mid<qr1 && ql1<=i->r && i->rc)
res=gcd(res, qry1(i->rc, ql1, qr1, ql2, qr2));
return res;
}
void init(int R, int C) {}
void update(int P, int Q, ll K)
{
upd1(&root, P, Q, K);
}
ll calculate(int P, int Q, int U, int V)
{
return qry1(&root, P, U, Q, V);
}
