#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int R, C, N, ch, P, Q, U, V;
long long K;
struct A
{
int s, e, left, right, ynum;
};
struct B
{
int s, e, left, right, onlyvalindex;
long long val;
};
vector<A> xTree;
vector<B> yTree;
long long gcd2(long long xx, long long yy)
{
if (yy == 0)
return xx;
return gcd2(yy, xx % yy);
}
void onevalyup(int num, int valco)
{
int s1 = yTree[num].s, e1 = yTree[num].e;
if ((s1 + e1) / 2 >= valco)
{
if (yTree[num].left == -1)
{
yTree[num].left = yTree.size();
yTree.push_back({s1, (s1 + e1) / 2, -1, -1, valco, yTree[num].val});
}
}
else
{
if (yTree[num].right == -1)
{
yTree[num].right = yTree.size();
yTree.push_back({(s1 + e1) / 2 + 1, e1, -1, -1, valco, yTree[num].val});
}
}
}
void yup(int num, int yco, long long v)
{
int s1 = yTree[num].s, e1 = yTree[num].e;
/*if (s1 == e1)
{
yTree[num].val = v;
yTree[num].onlyvalindex = yco;
return;
}*/
if (yTree[num].onlyvalindex == -1)
{
yTree[num].val = v;
yTree[num].onlyvalindex = yco;
return;
}
else if (yTree[num].onlyvalindex >= 0)
{
if (yTree[num].onlyvalindex == yco)
{
yTree[num].val = v;
return;
}
else
{
onevalyup(num, yTree[num].onlyvalindex);
yTree[num].onlyvalindex = -2;
}
}
if ((s1 + e1) / 2 >= yco)
{
if (yTree[num].left == -1)
{
yTree[num].left = yTree.size();
yTree.push_back({s1, (s1 + e1) / 2, -1, -1, -1, 0});
}
yup(yTree[num].left, yco, v);
}
else
{
if (yTree[num].right == -1)
{
yTree[num].right = yTree.size();
yTree.push_back({(s1 + e1) / 2 + 1, e1, -1, -1, -1, 0});
}
yup(yTree[num].right, yco, v);
}
long long l = 0, r = 0;
if (yTree[num].left >= 0)
l = yTree[yTree[num].left].val;
if (yTree[num].right >= 0)
r = yTree[yTree[num].right].val;
yTree[num].val = gcd2(l, r);
}
void hardyup(int num, int lnum, int rnum, int yco)
{
int s1 = yTree[num].s, e1 = yTree[num].e;
int nextl, nextr;
long long l = 0, r = 0;
int cnt = 0, valind;
if (lnum >= 0)
{
l = yTree[lnum].val;
if (yTree[lnum].onlyvalindex >= 0)
{
cnt++;
valind = yTree[lnum].onlyvalindex;
if (yTree[lnum].s != yTree[lnum].e)
onevalyup(lnum, yTree[lnum].onlyvalindex);
}
else if (yTree[lnum].onlyvalindex == -2)
cnt += 2;
}
if (rnum >= 0)
{
r = yTree[rnum].val;
if (yTree[rnum].onlyvalindex >= 0)
{
cnt++;
valind = yTree[rnum].onlyvalindex;
if (yTree[rnum].s != yTree[rnum].e)
onevalyup(rnum, yTree[rnum].onlyvalindex);
}
else if (yTree[rnum].onlyvalindex == -2)
cnt += 2;
}
if (cnt == 1)
yTree[num].onlyvalindex = valind;
else if (cnt > 1)
yTree[num].onlyvalindex = -2;
else
yTree[num].onlyvalindex = -1;
yTree[num].val = gcd2(l, r);
if (s1 == e1 || yTree[num].onlyvalindex >= 0 || yTree[num].onlyvalindex == -1)
return;
if (yco <= (s1 + e1) / 2)
{
if (lnum == -1)
nextl = -1;
else
nextl = yTree[lnum].left;
if (rnum == -1)
nextr = -1;
else
nextr = yTree[rnum].left;
if (yTree[num].left == -1)
{
yTree[num].left = yTree.size();
yTree.push_back({s1, (s1 + e1) / 2, -1, -1, -1, 0});
}
hardyup(yTree[num].left, nextl, nextr, yco);
}
else
{
if (lnum == -1)
nextl = -1;
else
nextl = yTree[lnum].right;
if (rnum == -1)
nextr = -1;
else
nextr = yTree[rnum].right;
if (yTree[num].right == -1)
{
yTree[num].right = yTree.size();
yTree.push_back({(s1 + e1) / 2 + 1, e1, -1, -1, -1, 0});
}
hardyup(yTree[num].right, nextl, nextr, yco);
}
}
void xup(int num, int xco, int yco, long long v)
{
int s1 = xTree[num].s, e1 = xTree[num].e;
if (s1 == e1)
{
yup(xTree[num].ynum, yco, v);
return;
}
if ((s1 + e1) / 2 >= xco)
{
if (xTree[num].left == -1)
{
xTree[num].left = xTree.size();
xTree.push_back({s1, (s1 + e1) / 2, -1, -1, int(yTree.size())});
yTree.push_back({0, C - 1, -1, -1, -1, 0});
}
xup(xTree[num].left, xco, yco, v);
}
else
{
if (xTree[num].right == -1)
{
xTree[num].right = xTree.size();
xTree.push_back({(s1 + e1) / 2 + 1, e1, -1, -1, int(yTree.size())});
yTree.push_back({0, C - 1, -1, -1, -1, 0});
}
xup(xTree[num].right, xco, yco, v);
}
int lynum = -1, rynum = -1;
if (xTree[num].left >= 0)
lynum = xTree[xTree[num].left].ynum;
if (xTree[num].right >= 0)
rynum = xTree[xTree[num].right].ynum;
hardyup(xTree[num].ynum, lynum, rynum, yco);
}
long long yans(int num, int py, int qy)
{
if (yTree[num].s > qy || yTree[num].e < py)
return 0ll;
if (yTree[num].onlyvalindex >= 0)
{
if (py <= yTree[num].onlyvalindex && yTree[num].onlyvalindex <= qy)
{
return yTree[num].val;
}
else
return 0ll;
}
if (py <= yTree[num].s && yTree[num].e <= qy)
return yTree[num].val;
long long l = 0, r = 0;
if (yTree[num].left >= 0)
l = yans(yTree[num].left, py, qy);
if (yTree[num].right >= 0)
r = yans(yTree[num].right, py, qy);
return gcd2(l, r);
}
long long xans(int num, int px, int qx, int py, int qy)
{
if (xTree[num].s > qx || xTree[num].e < px)
return 0ll;
if (px <= xTree[num].s && xTree[num].e <= qx)
{
return yans(xTree[num].ynum, py, qy);
}
long long l = 0, r = 0;
if (xTree[num].left >= 0)
l = xans(xTree[num].left, px, qx, py, qy);
if (xTree[num].right >= 0)
r = xans(xTree[num].right, px, qx, py, qy);
return gcd2(l, r);
}
void init(int RR, int CC)
{
R=RR;
C=CC;
xTree.push_back({0, R - 1, -1, -1, 0});
yTree.push_back({0, C - 1, -1, -1,-1, 0});
}
void update(int P,int Q,long long K)
{
xup(0, P, Q, K);
}
long long calculate(int P,int Q,int U,int V)
{
return xans(0, P, U, Q, V);
}
