#include "game.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int leftchild1[10400000], rightchild1[10400000], leftchild2[10400000], rightchild2[10400000];
ll segtree[10400000], large=1e9, cnt;
ll createNode()
{
return (cnt++);
}
void update2(ll i, ll l1, ll r1, ll l2, ll r2, ll x, ll y, ll z)
{
if (l2==r2)
{
if (l1==r1)
segtree[i]=z;
else
segtree[i]=gcd(segtree[leftchild1[i]], segtree[rightchild1[i]]);
return;
}
ll mid=(l2+r2)/2;
if (y<=mid)
{
if (!leftchild2[i])
leftchild2[i]=createNode();
leftchild1[leftchild2[i]]=leftchild2[leftchild1[i]];
rightchild1[leftchild2[i]]=leftchild2[rightchild1[i]];
update2(leftchild2[i], l1, r1, l2, mid, x, y, z);
}
else
{
if (!rightchild2[i])
rightchild2[i]=createNode();
leftchild1[rightchild2[i]]=rightchild2[leftchild1[i]];
rightchild1[rightchild2[i]]=rightchild2[rightchild1[i]];
update2(rightchild2[i], l1, r1, mid+1, r2, x, y, z);
}
segtree[i]=gcd(segtree[leftchild2[i]], segtree[rightchild2[i]]);
//cout << "segtree " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << " = " << segtree[i] << '\n';
}
void update1(ll i, ll l1, ll r1, ll x, ll y, ll z)
{
//cout << "update1 " << l1 << ' ' << r1 << '\n';
if (l1==r1)
{
update2(i, l1, r1, 0, large, x, y, z);
return;
}
ll mid=(l1+r1)/2;
if (x<=mid)
{
if (!leftchild1[i])
leftchild1[i]=createNode();
update1(leftchild1[i], l1, mid, x, y, z);
}
else
{
if (!rightchild1[i])
rightchild1[i]=createNode();
update1(rightchild1[i], mid+1, r1, x, y, z);
}
update2(i, l1, r1, 0, large, x, y, z);
}
ll query2(ll i, ll l1, ll r1, ll l2, ll r2, ll ql1, ll qr1, ll ql2, ll qr2)
{
if (ql2<=l2 && r2<=qr2)
return segtree[i];
ll mid=(l2+r2)/2, res=0;
if (l2<=qr2 && ql2<=mid && leftchild2[i])
res=gcd(res, query2(leftchild2[i], l1, r1, l2, mid, ql1, qr1, ql2, qr2));
if (mid<qr2 && ql2<=r2 && rightchild2[i])
res=gcd(res, query2(rightchild2[i], l1, r1, mid+1, r2, ql1, qr1, ql2, qr2));
return res;
}
ll query1(ll i, ll l1, ll r1, ll ql1, ll qr1, ll ql2, ll qr2)
{
if (ql1<=l1 && r1<=qr1)
return query2(i, l1, r1, 0, large, ql1, qr1, ql2, qr2);
ll mid=(l1+r1)/2, res=0;
if (l1<=qr1 && ql1<=mid && leftchild1[i])
res=gcd(res, query1(leftchild1[i], l1, mid, ql1, qr1, ql2, qr2));
if (mid<qr1 && ql1<=r1 && rightchild1[i])
res=gcd(res, query1(rightchild1[i], mid+1, r1, ql1, qr1, ql2, qr2));
return res;
}
void init(int R, int C)
{
createNode();
createNode();
}
void update(int P, int Q, ll K)
{
update1(1, 0, large, P, Q, K);
}
ll calculate(int P, int Q, int U, int V)
{
return query1(1, 0, large, P, U, Q, V);
}
