#include <bits/stdc++.h>
typedef long long ll;
typedef long double ldb;
const int md = (int)1e9 + 7;
const ll inf = 2e18;
const int OO = 1;
using namespace std;
#include "game.h"
/*
the struct 'element' must have:
* neutral element (as default constructor)
* operator *, to combine with a right operand and return the result
also note the "using T = ll". this is the range of indicies we allow. can change to int for efficiency.
*/
template<typename element>
struct segtree {
using T = ll;
struct node {
element val;
int l, r;
node(element v = element()) {
l = -1, r = -1, val = v;
}
};
T L, R;
vector<node> t;
segtree() {}
segtree(T LL, T RR) {
L = LL, R = RR;
t.push_back(node());
}
int add_node() {
t.push_back(node());
return (int)t.size() - 1;
}
int go_left(int v) {
if (t[v].l == -1) {
// this prevents a bug that might occur when t.push_back provokes reallocation
int x = add_node();
t[v].l = x;
}
return t[v].l;
}
int go_right(int v) {
if (t[v].r == -1) {
// this prevents a bug that might occur when t.push_back provokes reallocation
int x = add_node();
t[v].r = x;
}
return t[v].r;
}
void fix(int v) {
// assumes v has at least 1 child
if (t[v].l == -1) t[v].val = t[t[v].r].val;
else if (t[v].r == -1) t[v].val = t[t[v].l].val;
else t[v].val = t[t[v].l].val * t[t[v].r].val;
}
void update(T pos, element val) {
update(pos, val, 0, L, R);
}
void update(T pos, element val, int node, T nl, T nr) {
if (nl == nr) {
t[node].val = val;
return;
}
T mid = (nl + nr) / 2;
if (pos <= mid) update(pos, val, go_left(node), nl, mid);
else update(pos, val, go_right(node), mid + 1, nr);
fix(node);
}
element get(T i) {
int node = 0;
T l = L, r = R;
while (l < r) {
T mid = (l + r) / 2;
if (i <= mid) {
if (t[node].l == -1) return element();
node = t[node].l;
l = mid + 1;
}
else {
if (t[node].r == -1) return element();
node = t[node].r;
r = mid;
}
}
return t[node].val;
}
element query(T l, T r) {
if (l > r) return element();
return query(l, r, 0, L, R);
}
element query(T l, T r, int node, T nl, T nr) {
if (r < nl || nr < l) return element();
if (l <= nl && nr <= r) return t[node].val;
T mid = (nl + nr) / 2;
if (r <= mid || t[node].r == -1) {
if (t[node].l == -1) return element();
return query(l, r, go_left(node), nl, mid);
}
if (mid < l || t[node].l == -1)
return query(l, r, go_right(node), mid + 1, nr);
return query(l, r, t[node].l, nl, mid) * query(l, r, t[node].r, mid + 1, nr);
}
};
/*
the struct 'element' must have:
* neutral element (as default constructor)
* operator *, to combine with a right operand and return the result
also note the "using T = ll". this is the range of indicies we allow. can change to int for efficiency.
*/
template<typename element>
struct segtree2D {
using T = ll;
struct node {
segtree<element> val;
int l, r;
node() {}
node(T L, T R) {
l = -1, r = -1;
val = segtree<element>(L, R);
}
};
T L0, R0, L1, R1;
vector<node> t;
segtree2D() {}
segtree2D(T l0, T r0, T l1, T r1) {
L0 = l0;
R0 = r0;
L1 = l1;
R1 = r1;
t.push_back(node(L1, R1));
}
int add_node() {
t.push_back(node(L1, R1));
return (int)t.size() - 1;
}
int go_left(int v) {
if (t[v].l == -1) {
// this prevents a bug that might occur when t.push_back provokes reallocation
int x = add_node();
t[v].l = x;
}
return t[v].l;
}
int go_right(int v) {
if (t[v].r == -1) {
// this prevents a bug that might occur when t.push_back provokes reallocation
int x = add_node();
t[v].r = x;
}
return t[v].r;
}
void fix(int node, T pos1) {
// assumes node has at least 1 child
element val;
if (t[node].l == -1) val = t[t[node].r].val.get(pos1);
else if (t[node].r == -1) val = t[t[node].l].val.get(pos1);
else val = t[t[node].l].val.get(pos1) * t[t[node].r].val.get(pos1);
t[node].val.update(pos1, val);
}
void update(T pos0, T pos1, element val) {
update(pos0, pos1, val, 0, L0, R0);
}
void update(T pos0, T pos1, element val, int node, T nl, T nr) {
if (nl == nr) {
t[node].val.update(pos1, val);
return;
}
T mid = (nl + nr) / 2;
if (pos0 <= mid) update(pos0, pos1, val, go_left(node), nl, mid);
else update(pos0, pos1, val, go_right(node), mid + 1, nr);
fix(node, pos1);
}
element query(T l0, T r0, T l1, T r1) {
if (l0 > r0 || l1 > r1) return element();
return query(l0, r0, l1, r1, 0, L0, R0);
}
element query(T l0, T r0, T l1, T r1, int node, T nl, T nr) {
if (r0 < nl || nr < l0) return element();
if (l0 <= nl && nr <= r0) return t[node].val.query(l1, r1);
T mid = (nl + nr) / 2;
if (r0 <= mid || t[node].r == -1) {
if (t[node].l == -1) return element();
return query(l0, r0, l1, r1, go_left(node), nl, mid);
}
if (mid < l0 || t[node].l == -1)
return query(l0, r0, l1, r1, go_right(node), mid + 1, nr);
return query(l0, r0, l1, r1, t[node].l, nl, mid) * query(l0, r0, l1, r1, t[node].r, mid + 1, nr);
}
};
ll gcd(ll x, ll y) {
return !y ? x : gcd(y, x % y);
}
struct ele {
ll x;
ele(ll xx = 0) : x(xx) {}
ele operator * (const ele &a) const {
return ele(gcd(x, a.x));
}
};
segtree2D<ele> T;
void init(int R, int C) {
T = segtree2D<ele>(0, R - 1, 0, C - 1);
}
void update(int p, int q, ll k) {
T.update(p, q, k);
}
ll calculate(int p, int q, int u, int v) {
return T.query(p, u, q, v).x;
}
