#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ii = pair<int,int>;
using ll = long long;
constexpr int MAXN = 5 + 2000;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
#define m ((s+e)/2)
struct segtree {
struct Node {
ll val;
Node* l, *r;
Node() : val(0), l(nullptr), r(nullptr) {}
};
Node* root = new Node();
segtree() = default;
ll query(int s, int e, Node* curr, int l, int r) {
if (l > r || curr == nullptr) return 0;
if (s == l && e == r) return curr->val;
return gcd(query(s, m, curr->l, l, min(m,r)), query(1+m, e, curr->r, max(1+m,l), r));
}
void update(int s, int e, Node* curr, int l, int r, ll add) {
if (l > r) return;
if (s == l && e == r) {
curr->val = add;
} else {
if (curr->l == nullptr) curr->l = new Node();
if (curr->r == nullptr) curr->r = new Node();
update(s, m, curr->l, l, min(m,r), add);
update(1+m, e, curr->r, max(1+m,l), r, add);
curr->val = gcd(curr->l->val, curr->r->val);
}
}};
namespace input {int R,C;}
namespace stree2d {
struct Node2d {
segtree t;
Node2d* l, *r;
Node2d() : l(nullptr), r(nullptr) {}
};
Node2d* root = new Node2d();
ll query(int s, int e, Node2d* curr, int l, int r, int sy, int ey) {
if (l > r || curr == nullptr) return 0;
if (s == l && e == r) return curr->t.query(1, input::C, curr->t.root, sy, ey);
ll le = query(s, m, curr->l, l, min(m,r), sy, ey);
ll ri = query(1+m, e, curr->r, max(1+m,l), r, sy, ey);
return gcd(le,ri);
}
void update(int s, int e, Node2d* curr, int l, int r, int sy, int ey, ll add) {
if (l > r) return;
if (s == l && e == r) {
curr->t.update(1, input::C, curr->t.root, sy, ey, add);
} else {
if (curr->l == nullptr) curr->l = new Node2d();
if (curr->r == nullptr) curr->r = new Node2d();
update(s, m, curr->l, l, min(m,r), sy, ey, add);
update(1+m, e, curr->r, max(1+m,l), r, sy, ey, add);
ll newval = gcd(curr->l->t.query(1, input::C, curr->l->t.root, sy, ey),
curr->r->t.query(1, input::C, curr->r->t.root, sy, ey));
curr->t.update(1, input::C, curr->t.root, sy, sy, newval);
}
}}
void init(int R, int C) {
input::R = R;
input::C = C;
}
void update(int P, int Q, long long K) {
++P; ++Q;
stree2d::update(1, input::R, stree2d::root, P, P, Q, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
++P; ++Q; ++U; ++V;
return stree2d::query(1, input::R, stree2d::root, P, U, Q, V);
}
