#include "game.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
node *lc1=0, *rc1=0, *lc2=0, *rc2=0;
int l1=0, r1=1e9, l2=0, r2=1e9;
ll val=0;
} root;
void upd2(node *i, ll x, ll y, ll z)
{
//cout << "upd2 " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << '\n';
//if (i->lc1)
// cout << "left child exists\n";
//if (i->rc1)
// cout << "right child exists\n";
if (i->l2==i->r2)
{
if (i->l1==i->r1)
i->val=z;
else
i->val=gcd(i->lc1?i->lc1->val:0, i->rc1?i->rc1->val:0);
//cout << "SEGGGGGGG " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << ' ' << i->val << '\n';
return;
}
ll mid=(i->l2+i->r2)/2;
if (y<=mid)
{
if (!i->lc2)
{
i->lc2=new node;
i->lc2->l1=i->l1;
i->lc2->r1=i->r1;
i->lc2->l2=i->l2;
i->lc2->r2=mid;
}
if (i->lc1)
i->lc2->lc1=i->lc1->lc2;
if (i->rc1)
i->lc2->rc1=i->rc1->lc2;
upd2(i->lc2, x, y, z);
}
else
{
if (!i->rc2)
{
i->rc2=new node;
i->rc2->l1=i->l1;
i->rc2->r1=i->r1;
i->rc2->l2=mid+1;
i->rc2->r2=i->r2;
}
if (i->lc1)
i->rc2->lc1=i->lc1->rc2;
if (i->rc1)
i->rc2->rc1=i->rc1->rc2;
upd2(i->rc2, x, y, z);
}
if (i->l1==i->r1)
i->val=gcd(i->lc2?i->lc2->val:0, i->rc2?i->rc2->val:0);
else
i->val=gcd(i->lc1?i->lc1->val:0, i->rc1?i->rc1->val:0);
//cout << "SEGGGGGGG " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << ' ' << i->val << '\n';
}
//int cnt=0;
void upd1(node *i, ll x, ll y, ll z)
{
//if (cnt<=10)
// cout << "upd1 " << i->l1 << ' ' << i->r1 << '\n';
//cnt++;
if (i->l1==i->r1)
{
upd2(i, x, y, z);
return;
}
ll mid=(i->l1+i->r1)/2;
if (x<=mid)
{
if (!i->lc1)
{
i->lc1=new node;
i->lc1->l1=x;
i->lc1->r1=x;
}
else if (x<i->lc1->l1 || x>i->lc1->r1)
{
ll l=i->l1, r=i->r1;
while (1)
{
ll m=(l+r)/2;
if ((x<=m)^(i->lc1->r1<=m))
break;
if (x<=m)
r=m;
else
l=m+1;
}
node *j=new node;
j->l1=l;
j->r1=r;
if (x<=(l+r)/2)
j->rc1=i->lc1;
else
j->lc1=i->lc1;
i->lc1=j;
}
upd1(i->lc1, x, y, z);
}
else
{
//if (cnt<=10)
// cout << "here\n";
if (!i->rc1)
{
//if (cnt<=10)
// cout << "here\n";
i->rc1=new node;
i->rc1->l1=x;
i->rc1->r1=x;
}
else if (x<i->rc1->l1 || x>i->rc1->r1)
{
ll l=i->l1, r=i->r1;
int cnt=0;
while (1)
{
if (cnt<=20)
cout << l << ' ' << r << ' ' << i->rc1->l1 << ' ' << i->rc1->r1 << '\n';
if (cnt<=20)
cnt++;
ll m=(l+r)/2;
if ((x<=m)^(i->rc1->r1<=m))
break;
if (x<=m)
r=m;
else
l=m+1;
}
node *j=new node;
j->l1=l;
j->r1=r;
if (x<=(l+r)/2)
j->rc1=i->rc1;
else
j->lc1=i->rc1;
i->rc1=j;
}
upd1(i->rc1, x, y, z);
}
upd2(i, x, y, z);
}
ll qry2(node *i, ll ql1, ll qr1, ll ql2, ll qr2)
{
//cout << "qry2 " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << ' ' << i->val << '\n';
if (ql2<=i->l2 && i->r2<=qr2)
return i->val;
ll mid=(i->l2+i->r2)/2, res=0;
if (i->l2<=qr2 && ql2<=mid)
{
if (!i->lc2)
{
i->lc2=new node;
i->lc2->l1=i->l1;
i->lc2->r1=i->r1;
i->lc2->l2=i->l2;
i->lc2->r2=mid;
}
if (i->lc1)
i->lc2->lc1=i->lc1->lc2;
if (i->rc1)
i->lc2->rc1=i->rc1->lc2;
if (i->lc2->l1==i->lc2->r1)
{
if (i->lc2->l2<i->lc2->r2)
i->lc2->val=gcd(i->lc2->lc2?i->lc2->lc2->val:0, i->lc2->rc2?i->lc2->rc2->val:0);
}
else
i->lc2->val=gcd(i->lc2->lc1?i->lc2->lc1->val:0, i->lc2->rc1?i->lc2->rc1->val:0);
res=gcd(res, qry2(i->lc2, ql1, qr1, ql2, qr2));
}
if (mid<qr2 && ql2<=i->r2)
{
if (!i->rc2)
{
i->rc2=new node;
i->rc2->l1=i->l1;
i->rc2->r1=i->r1;
i->rc2->l2=mid+1;
i->rc2->r2=i->r2;
}
if (i->lc1)
i->rc2->lc1=i->lc1->rc2;
if (i->rc1)
i->rc2->rc1=i->rc1->rc2;
if (i->rc2->l1==i->rc2->r1)
{
if (i->rc2->l2<i->rc2->r2)
i->rc2->val=gcd(i->rc2->lc2?i->rc2->lc2->val:0, i->rc2->rc2?i->rc2->rc2->val:0);
}
else
i->rc2->val=gcd(i->rc2->lc1?i->rc2->lc1->val:0, i->rc2->rc1?i->rc2->rc1->val:0);
res=gcd(res, qry2(i->rc2, ql1, qr1, ql2, qr2));
}
return res;
}
ll qry1(node *i, ll ql1, ll qr1, ll ql2, ll qr2)
{
//cout << "qry1 " << i->l1 << ' ' << i->r1 << ' ' << i->l2 << ' ' << i->r2 << ' ' << i->val << '\n';
if (ql1<=i->l1 && i->r1<=qr1)
return qry2(i, ql1, qr1, ql2, qr2);
ll mid=(i->l1+i->r1)/2, res=0;
if (i->l1<=qr1 && ql1<=mid && i->lc1)
res=gcd(res, qry1(i->lc1, ql1, qr1, ql2, qr2));
if (mid<qr1 && ql1<=i->r1 && i->rc1)
res=gcd(res, qry1(i->rc1, 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);}
