#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;
const ll INF = 1e9 + 1;
ll sg1[MAXN1], sg2[MAXN2], sz1, sz2, R, C;
int bl1[MAXN1], br1[MAXN1], bl2[MAXN2], br2[MAXN2], lc1[MAXN1], rc1[MAXN1], lc2[MAXN2], rc2[MAXN2];
inline int node2(int l, int r) {
int v = ++sz2;
bl2[v] = l;
br2[v] = r;
return v;
}
inline int node1(int l, int r) {
int v = ++sz1;
sg1[v] = node2(0, C);
bl1[v] = l;
br1[v] = r;
return v;
}
void update2_line(int y, ll val, int v) {
if (bl2[v] == br2[v]) {
sg2[v] = val;
return;
}
int mid = (bl2[v] + br2[v]) >> 1;
if (y <= mid) {
if (!lc2[v]) lc2[v] = node2(bl2[v], mid);
update2_line(y, val, lc2[v]);
} else {
if (!rc2[v]) rc2[v] = node2(mid + 1, br2[v]);
update2_line(y, val, rc2[v]);
}
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) {
sg2[v] = gcd(sg2[par_l], sg2[par_r]);
if (bl2[v] == br2[v]) return;
int mid = (bl2[v] + br2[v]) >> 1;
if (y <= mid) {
if (!lc2[v]) lc2[v] = node2(bl2[v], mid);
update2_seg(y, val, lc2[v], lc2[par_l], lc2[par_r]);
} else {
if (!rc2[v]) rc2[v] = node2(mid + 1, br2[v]);
update2_seg(y, val, rc2[v], rc2[par_l], rc2[par_r]);
}
}
void update1(int x, int y, ll val, int v) {
if (bl1[v] == br1[v]) update2_line(y, val, sg1[v]);
else {
int mid = (bl1[v] + br1[v]) >> 1;
if (x <= mid) {
if (!lc1[v]) lc1[v] = node1(bl1[v], mid);
update1(x, y, val, lc1[v]);
} else {
if (!rc1[v]) rc1[v] = node1(mid + 1, br1[v]);
update1(x, y, val, rc1[v]);
}
update2_seg(y, val, sg1[v], sg1[lc1[v]], sg1[rc1[v]]);
}
}
ll query2(int cl, int cr, int v) {
if (v == 0 || cl > br2[v] || cr < bl2[v]) return 0;
if (cl <= bl2[v] && cr >= br2[v]) return sg2[v];
return gcd(query2(cl, cr, lc2[v]),
query2(cl, cr, rc2[v]));
}
ll query1(int rl, int rr, int cl, int cr, int v) {
if (v == 0 || rl > br1[v] || rr < bl1[v]) return 0; // optimize v == 0
if (rl <= bl1[v] && rr >= br1[v]) {
return query2(cl, cr, sg1[v]);
}
return gcd(query1(rl, rr, cl, cr, lc1[v]),
query1(rl, rr, cl, cr, rc1[v]));
}
void init(int R_, int C_) {
R = R_, C = C_;
sg1[1] = 1;
bl1[1] = 0, br1[1] = R, bl2[1] = 0, br2[1] = C;
sz1 = sz2 = 1;
}
void update(int P, int Q, ll K) {
update1(P, Q, K, 1);
}
long long calculate(int P, int Q, int U, int V) {
return query1(P, U, Q, V, 1);
}
// TODO: change MAXN
// TODO: change init bounds
// TODO: use gcd2
