#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define boost() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int n, m, q;
struct node1d {
node1d(int v, int x, int y) : v(v), x(x), y(y), l(NULL), r(NULL) {}
ll v;
int x, y; // range
node1d *l, *r;
};
struct node2d {
node2d() : l(NULL), r(NULL), segtree(0, 1, m) {}
node2d *l, *r;
node1d segtree;
} *root;
void update1d(node1d *root, int i, ll v) {
int s = root->x, e = root->y, mid = (s + e) >> 1;
if (s == e) {
root->v = v;
return;
}
node1d **child = &(i <= mid ? root->l : root->r);
if (*child == NULL) {
*child = new node1d(v, i, i);
(*child)->v = v;
} else if ((*child)->x <= i && i <= (*child)->y) {
update1d(*child, i, v);
} else {
do {
if (i <= mid) e = mid;
else s = mid + 1;
mid = (s + e) >> 1;
} while ((i <= mid) == ((*child)->y <= mid));
node1d *node2 = new node1d(0, s, e);
if ((*child)->y <= mid) node2->l = *child;
else node2->r = *child;
*child = node2;
update1d(*child, i, v);
}
root->v = __gcd(root->l ? root->l->v : 0, root->r ? root->r->v : 0);
}
ll calculate1d(node1d *root, int l, int r) {
if (root == NULL || root->x > r || root->y < l) return 0;
if (l <= root->x && root->y <= r) {
return root->v;
}
return __gcd(calculate1d(root->l, l, r), calculate1d(root->r, l, r));
}
void update2d(node2d *root, int l, int r, int x, int y, ll v) {
if (l == r) {
update1d(&root->segtree, y, v);
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
if (root->l == NULL) root->l = new node2d();
update2d(root->l, l, mid, x, y, v);
} else {
if (root->r == NULL) root->r = new node2d();
update2d(root->r, mid+1, r, x, y, v);
}
ll value = __gcd(root->l ? calculate1d(&root->l->segtree, y, y) : 0, root->r ? calculate1d(&root->r->segtree, y, y) : 0);
update1d(&root->segtree, y, value);
}
ll calculate2d(node2d *root, int l, int r, int x, int y, int x2, int y2) {
if (root == NULL || l > x2 || r < x) return 0;
if (x <= l && r <= x2) return calculate1d(&root->segtree, y, y2);
int mid = (l + r) >> 1;
return __gcd(calculate2d(root->l, l, mid, x, y, x2, y2), calculate2d(root->r, mid+1, r, x, y, x2, y2));
}
void init(int n, int m) {
::n = n;
::m = m;
root = new node2d();
}
void update(int x, int y, ll v) {
++x, ++y;
update2d(root, 1, n, x, y, v);
}
ll calculate(int x, int y, int x2, int y2) {
++x, ++y, ++x2, ++y2;
return calculate2d(root, 1, n, x, y, x2, y2);
}
