#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sep ' '
#define debug(x) //cerr << #x << ": " << x << endl;
const ll MAXN1 = 1e6 + 10;
const ll MAXN2 = 2e7 + 10;
const ll INF = 1e9 + 1;
ll sg1[MAXN1], sg2[MAXN2], sz1, sz2, R, C;
int lc1[MAXN1], rc1[MAXN1], O[MAXN2];
// TODO: create node2 when neede
// O[v] < 0 => bache chap++ age -inf nabashe bache rast -O[v] va ...
inline int lc2(int v) {
if (O[v] == 0) return 0;
if (O[v] < 0) return v + 1;
if (O[v] == INF) return 0;
return O[v];
}
inline int rc2(int v) {
if (O[v] == 0) return 0;
if (O[v] > 0) return v + 1;
if (-O[v] == INF) return 0;
return -O[v];
}
inline int node2() {
int v = ++sz2;
//cerr << "what is this: " << v << endl;
return v;
}
inline void cl(int v) {
//cerr << "cl: " << v << endl;
if (!O[v]) O[v] = -INF, node2();
else O[v] = node2();
}
inline void cr(int v) {
//cerr << "cr: " << v << endl;
if (!O[v]) O[v] = INF, node2();
else O[v] = -node2();
}
inline int node1() {
int v = ++sz1;
return v;
}
void update2_line(int y, ll val, int v, int bl2, int br2) {
debug(v)
if (bl2 == br2) {
sg2[v] = val;
return;
}
int mid = (bl2 + br2) >> 1;
if (y <= mid) {
debug("laanati left")
debug(O[v])
if (!lc2(v)) cl(v);
update2_line(y, val, lc2(v), bl2, mid);
} else {
debug("laanati rast")
debug(O[v])
if (!rc2(v)) cr(v);
update2_line(y, val, rc2(v), mid + 1, br2);
}
sg2[v] = gcd(sg2[lc2(v)], sg2[rc2(v)]); // optimize
}
void update2_seg(int y, ll val, int v, int par_l, int par_r, int bl2, int br2) {
debug(v)
sg2[v] = gcd(sg2[par_l], sg2[par_r]);
if (bl2 == br2) return;
int mid = (bl2 + br2) >> 1;
if (y <= mid) {
debug("laaanati left")
debug(O[v])
if (!lc2(v)) cl(v);
debug(O[v])
update2_seg(y, val, lc2(v), lc2(par_l), lc2(par_r), bl2, mid);
} else {
debug("lanaati rast")
if (!rc2(v)) cr(v);
update2_seg(y, val, rc2(v), rc2(par_l), rc2(par_r), mid + 1, br2);
}
}
inline int sg1c(int v) {
if (!sg1[v]) {
sg1[v] = node2();
}
return sg1[v];
}
void update1(int x, int y, ll val, int v, int bl1, int br1) {
if (bl1 == br1) {
// //cerr << "still fucking update1: " << bl1 << sep << br1 << endl << "and we are updating line : " << y << sep << val << endl;
update2_line(y, val, sg1c(v), 0, C);
} else {
int mid = (bl1 + br1) >> 1;
if (x <= mid) {
if (!lc1[v]) lc1[v] = node1();
update1(x, y, val, lc1[v], bl1, mid);
} else {
if (!rc1[v]) rc1[v] = node1();
update1(x, y, val, rc1[v], mid + 1, br1);
}
//cerr << "fucking update seg: " << bl1 << sep << br1 << sep << y << sep << val << endl;
// //cerr << "still fucking update1: " << bl1 << sep << br1 << endl << "and we are updating segment: " << y << sep << val << endl;
update2_seg(y, val, sg1c(v), sg1[lc1[v]], sg1[rc1[v]], 0, C);
}
}
ll query2(int cl, int cr, int v, int bl2, int br2) {
if (v == 0 || cl > br2 || cr < bl2) return 0;
if (cl <= bl2 && cr >= br2) return sg2[v];
int mid = (bl2 + br2) >> 1;
return gcd(query2(cl, cr, lc2(v), bl2, mid),
query2(cl, cr, rc2(v), mid + 1, br2));
}
ll query1(int rl, int rr, int cl, int cr, int v, int bl1, int br1) {
if (v == 0 || rl > br1 || rr < bl1) return 0; // optimize v == 0
if (rl <= bl1 && rr >= br1) {
return query2(cl, cr, sg1[v], 0, C);
}
int mid = (bl1 + br1) >> 1;
return gcd(query1(rl, rr, cl, cr, lc1[v], bl1, mid),
query1(rl, rr, cl, cr, rc1[v], mid + 1, br1));
}
void init(int R_, int C_) {
R = R_, C = C_;
sz1 = sz2 = 1;
}
void update(int P, int Q, ll K) {
update1(P, Q, K, 1, 0, R);
//cerr << "________________________________________________________" << endl;
}
long long calculate(int P, int Q, int U, int V) {
return query1(P, U, Q, V, 1, 0, R);
}
// TODO: change MAXN
// TODO: change init bounds
// TODO: use gcd2
