#include "game.h"
#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Node1 {
int n, ln, rn; // left node, right node
Node1() : n(-1), ln(-1), rn(-1) {}
};
struct Node2 {
int ln, rn, latest;
ll val;
Node2() : ln(-1), rn(-1), val(0), latest(-1) {}
};
int R, C;
vector<Node1> node1;
vector<Node2> node2;
int new_node1() {
node1.push_back(Node1());
return node1.size()-1;
}
int new_node2() {
node2.push_back(Node2());
return node2.size()-1;
}
void update2(int n, int nl, int nr, int y, ll v) {
if (nl == nr) {
node2[n].val = v;
return;
}
int mid = (nl + nr) / 2;
if (node2[n].latest != -1) {
if (node2[n].latest <= mid) {
node2[n].ln = new_node2();
node2[node2[n].ln].latest = node2[n].latest;
node2[node2[n].ln].val = node2[n].val;
} else {
node2[n].rn = new_node2();
node2[node2[n].rn].latest = node2[n].latest;
node2[node2[n].rn].val = node2[n].val;
}
node2[n].latest = -1;
}
if (y <= mid) {
if (node2[n].ln == -1) {
node2[n].ln = new_node2();
node2[node2[n].ln].latest = y;
node2[node2[n].ln].val = v;
} else {
update2(node2[n].ln, nl, mid, y, v);
}
} else {
if (node2[n].rn == -1) {
node2[n].rn = new_node2();
node2[node2[n].rn].latest = y;
node2[node2[n].rn].val = v;
} else {
update2(node2[n].rn, mid+1, nr, y, v);
}
}
ll upd_gcd = 0;
if (node2[n].ln != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].ln].val);
if (node2[n].rn != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].rn].val);
node2[n].val = upd_gcd;
}
ll query2(int n, int nl, int nr, int l, int r) {
if (r < nl || nr < l) return 0;
if (l <= nl && nr <= r) return node2[n].val;
if (node2[n].latest != -1) {
return (l <= node2[n].latest && node2[n].latest <= r ? node2[n].val : 0);
}
ll ret = 0;
int mid = (nl + nr) / 2;
if (node2[n].ln != -1) ret = gcd2(ret, query2(node2[n].ln, nl, mid, l, r));
if (node2[n].rn != -1) ret = gcd2(ret, query2(node2[n].rn, mid+1, nr, l, r));
return ret;
}
void update1(int n, int nl, int nr, int x, int y, ll v) {
if (node1[n].n == -1) node1[n].n = new_node2();
if (nl == nr) {
update2(node1[n].n, 0, C-1, y, v);
return;
}
int mid = (nl + nr) / 2;
if (x <= mid) {
if (node1[n].ln == -1) node1[n].ln = new_node1();
update1(node1[n].ln, nl, mid, x, y, v);
} else {
if (node1[n].rn == -1) node1[n].rn = new_node1();
update1(node1[n].rn, mid+1, nr, x, y, v);
}
ll upd_gcd = 0;
if (node1[n].ln != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].ln].n, 0, C-1, y, y));
if (node1[n].rn != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].rn].n, 0, C-1, y, y));
update2(node1[n].n, 0, C-1, y, upd_gcd);
}
ll query1(int n, int nl, int nr, int x1, int y1, int x2, int y2) {
if (nr < x1 || x2 < nl) return 0;
if (x1 <= nl && nr <= x2) return (node1[n].n != -1 ? query2(node1[n].n, 0, C-1, y1, y2) : 0);
ll ret = 0;
int mid = (nl + nr) / 2;
if (node1[n].ln != -1) ret = gcd2(ret, query1(node1[n].ln, nl, mid, x1, y1, x2, y2));
if (node1[n].rn != -1) ret = gcd2(ret, query1(node1[n].rn, mid+1, nr, x1, y1, x2, y2));
return ret;
}
int root;
void init(int _R, int _C) {
R = _R;
C = _C;
root = new_node1();
}
void update(int P, int Q, ll K) {
update1(root, 0, R-1, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return query1(root, 0, R-1, P, Q, U, V);
}
