#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
constexpr int MAXQ = 23000;
#define left lft
#define right rght
#define gcd my_gcd
ll my_gcd(ll a, ll b) {
if (!a || !b) return a ^ b;
ll c;
while ((c = a % b)) {
a = b;
b = c;
}
return b;
}
int R, C;
constexpr int M = MAXQ * 30 * 30 + 10;
int counter = 1;
ll d[M];
int left[M], right[M];
//vector<ll> d{{}};
//vector<int> left{{}}, right{{}};
int st_create(int l, int r) {
// d.emplace_back(), left.emplace_back(), right.emplace_back();
return counter++;
}
int pa[30];
void st_update(int v, int i, ll k, int l, int r) {
int kek = 0;
while (l + 1 < r) {
int mid = (l + r) / 2;
pa[kek++] = v;
if (i < mid) {
if (!left[v]) {
left[v] = st_create(l, mid);
}
v = left[v];
r = mid;
} else {
if (!right[v]) {
right[v] = st_create(mid, r);
}
v = right[v];
l = mid;
}
}
d[v] = k;
for (int x = kek - 1; x >= 0; --x) {
v = pa[x];
d[v] = gcd(d[left[v]], d[right[v]]);
}
}
ll st_query(int v, int lx, int rx, int l, int r) {
if (lx >= r || rx <= l) {
return 0;
} else if (lx <= l && r <= rx) {
return d[v];
} else {
int mid = (l + r) / 2;
ll ans = 0;
if (left[v]) {
ans = gcd(ans, st_query(left[v], lx, rx, l, mid));
}
if (right[v]) {
ans = gcd(ans, st_query(right[v], lx, rx, mid, r));
}
return ans;
}
}
ll st_query_simple(int v, int i, int l, int r) {
while (l + 1 < r && v) {
int mid = (l + r) / 2;
if (i < mid) {
v = left[v];
r = mid;
} else {
v = right[v];
l = mid;
}
}
return d[v];
}
struct SegmentTree {
int st = 0;
int left = 0, right = 0;
};
constexpr int N = MAXQ * 30 + 10;
SegmentTree t[N];
//vector<SegmentTree> t{{}};
int node_counter = 1;
int create(int l, int r) {
// t[node_counter] = SegmentTree({l, r});
// t.emplace_back();
return node_counter++;
}
void build_st(int x) {
if (!t[x].st) {
t[x].st = st_create(0, C);
}
}
ll simple_query(int x, int y) {
if (!t[x].st) {
return 0;
} else {
return st_query_simple(t[x].st, y, 0, C);
}
}
void update(int v, int x, int y, ll k, int l, int r) {
build_st(v);
if (l + 1 == r) {
st_update(t[v].st, y, k, 0, C);
} else {
int mid = (l + r) / 2;
if (x < mid) {
if (!t[v].left) {
t[v].left = create(l, mid);
}
update(t[v].left, x, y, k, l, mid);
} else {
if (!t[v].right) {
t[v].right = create(mid, r);
}
update(t[v].right, x, y, k, mid, r);
}
st_update(t[v].st, y, gcd(simple_query(t[v].left, y), simple_query(t[v].right, y)), 0, C);
}
}
ll query(int v, int lx, int rx, int ly, int ry, int l, int r) {
if (l >= rx || lx >= r || !t[v].st) {
return 0;
} else if (lx <= l && r <= rx) {
return st_query(t[v].st, ly, ry, 0, C);
} else {
int mid = (l + r) / 2;
ll ans = 0;
if (t[v].left) {
ans = gcd(ans, query(t[v].left, lx, rx, ly, ry, l, mid));
}
if (t[v].right) {
ans = gcd(ans, query(t[v].right, lx, rx, ly, ry, mid, r));
}
return ans;
}
}
void init(int R, int C) {
::R = R, ::C = C;
create(0, R);
}
void update(int P, int Q, ll K) {
update(1, P, Q, K, 0, R);
}
ll calculate(int P, int Q, int U, int V) {
return query(1, P, U + 1, Q, V + 1, 0, R);
}
