#include "game.h"
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
struct updateVal
{
int R;
int C;
ll V;
};
const ll W = 1200000, WW = 13000000;
ll value[WW];
int updateIndex[WW]; // index in array updates
vector<updateVal> updates;
int ls[WW], rs[WW], lsy[W], rsy[W], root[W];
int sz = 2, sz2 = 2, Root = 1;
int n, m;
ll qans;
ll gcd(ll a, ll b) {
while (a && b) {
(a > b) ? a %= b : b %= a;
}
return a + b;
}
void queryX(int &v, int C1, int C2, int vleft, int vright) {
if (vright < C1 || vleft > C2) return;
if (vleft >= C1 && vright <= C2) {
qans = gcd(qans, value[v]);
return;
}
if (ls[v] == 0 && rs[v] == 0) {
qans = gcd(qans, value[v]);
return;
}
int mid = (vleft + vright) / 2;
queryX(ls[v], C1, C2, vleft, mid);
queryX(rs[v], C1, C2, mid + 1, vright);
}
void queryXWithCheck(int v, int C) {
if (updateIndex[v] != -1) {
if (updates[updateIndex[v]].C == C)
qans = gcd(qans, updates[updateIndex[v]].V);
}
else {
queryX(root[v], C, C, 1, m);
}
}
void queryY(int &v, int R1, int C1, int R2, int C2, int vleft, int vright) {
if (v == 0) return;
if (vleft > R2 || vright < R1) {
return;
}
if (updateIndex[v] != -1) {
if (updates[updateIndex[v]].R >= R1 && updates[updateIndex[v]].R <= R2 &&
updates[updateIndex[v]].C >= C1 && updates[updateIndex[v]].C <= C2)
qans = gcd(qans, updates[updateIndex[v]].V);
return;
}
if (vleft >= R1 && vright <= R2) {
queryX(root[v], C1, C2, 1, m);
return;
}
int mid = (vleft + vright) / 2;
queryY(lsy[v], R1, C1, R2, C2, vleft, mid);
queryY(rsy[v], R1, C1, R2, C2, mid + 1, vright);
}
void Updatex(int &v, int C, ll val, int vleft, int vright) {
if (vleft > C || vright < C) return;
if (v == 0) v = ++sz;
if (vleft == vright) {
value[v] = val;
return;
}
int mid = (vleft + vright) / 2;
if (C <= mid) Updatex(ls[v], C, val, vleft, mid);
else Updatex(rs[v], C, val, mid + 1, vright);
value[v] = 0;
if (ls[v]) value[v] = gcd(value[v], value[ls[v]]);
if (rs[v]) value[v] = gcd(value[v], value[rs[v]]);
return;
}
void Updatey(int &v, int R, int C, ll val, int vleft, int vright) {
if (vleft > R || vright < R) return;
if (v == 0) {
v = ++sz2;
}
if (vleft == vright) {
Updatex(root[v], C, val, 1, m);
return;
}
if (updateIndex[v] == -1 && lsy[v] == 0 && rsy[v] == 0) {
updates.push_back({ R, C, val });
updateIndex[v] = updates.size() - 1;
return;
}
int mid = (vleft + vright) / 2;
if (updateIndex[v] != -1) {
if (updates[updateIndex[v]].R <= mid)
{
Updatey(lsy[v], updates[updateIndex[v]].R,
updates[updateIndex[v]].C, updates[updateIndex[v]].V,
vleft, mid);
}
else {
Updatey(rsy[v], updates[updateIndex[v]].R,
updates[updateIndex[v]].C, updates[updateIndex[v]].V,
mid + 1, vright);
}
qans = 0;
if (lsy[v]) {
queryXWithCheck(lsy[v], updates[updateIndex[v]].C);
}
if (rsy[v]) {
queryXWithCheck(rsy[v], updates[updateIndex[v]].C);
}
Updatex(root[v], updates[updateIndex[v]].C, qans, 1, m);
updateIndex[v] = -1;
}
if (R <= mid)
{
Updatey(lsy[v], R, C, val, vleft, mid);
}
else
{
Updatey(rsy[v], R, C, val, mid + 1, vright);
}
qans = 0;
if (lsy[v]) {
queryXWithCheck(lsy[v], C);
}
if (rsy[v]) {
queryXWithCheck(rsy[v], C);
}
Updatex(root[v], C, qans, 1, m);
}
void init(int R, int C) {
n = R;
m = C;
Root = 1;
for (int i = 0; i < WW; ++i)
updateIndex[i] = -1;
}
void update(int R, int Q, long long K) {
Updatey(Root, R + 1, Q + 1, K, 1, n);
}
long long calculate(int P, int Q, int U, int V) {
qans = 0;
queryY(Root, P + 1, Q + 1, U + 1, V + 1, 1, n);
return qans;
}
