#include "game.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int r, c;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct segment {
struct node {
ll val;
node *l, *r;
node() : val(0), l(nullptr), r(nullptr) {}
};
typedef node* pnode;
pnode rt;
segment() : rt(nullptr) {}
void upd (int l, int r, pnode &cur, int pos, ll val) {
if (!cur) cur = new node();
if (l == r) return void(cur->val = val);
int mid = (l + r) >> 1;
if (pos <= mid) upd(l, mid, cur->l, pos, val);
else upd(mid + 1, r, cur->r, pos, val);
cur->val = gcd2(cur->l ? cur->l->val : 0, cur->r ? cur->r->val : 0);
}
ll qr (int l, int r, pnode cur, int tl, int tr) {
if (l > tr || r < tl || !cur) return 0;
if (l >= tl && r <= tr) return cur->val;
int mid = (l + r) >> 1;
return gcd2(qr(l, mid, cur->l, tl, tr), qr(mid + 1, r, cur->r, tl, tr));
}
};
struct segment2 {
struct node {
segment val;
node *l, *r;
node() : val(segment()), l(nullptr), r(nullptr) {}
};
typedef node* pnode;
pnode rt;
segment2() : rt(nullptr) {}
ll get (pnode t, int posy) {
return t ? t->val.qr(0, c - 1, t->val.rt, posy, posy) : 0;
}
void upd (int l, int r, pnode &cur, int posx, int posy, ll val) {
if (!cur) cur = new node();
if (l < r) {
int mid = (l + r) >> 1;
if (posx <= mid) upd(l, mid, cur->l, posx, posy, val);
else upd(mid + 1, r, cur->r, posx, posy, val);
val = gcd2(get(cur->l, posy), get(cur->r, posy));
}
cur->val.upd(0, c - 1, cur->val.rt, posy, val);
}
ll qr (int l, int r, pnode cur, int tlx, int trx, int tly, int _try) {
if (l > trx || r < tlx || !cur) return 0;
if (l >= tlx && r <= trx) return cur->val.qr(0, c - 1, cur->val.rt, tly, _try);
int mid = (l + r) >> 1;
return gcd2(qr(l, mid, cur->l, tlx, trx, tly, _try), qr(mid + 1, r, cur->r, tlx, trx, tly, _try));
}
} segm;
void init(int R, int C) {
r = R; c = C;
/* ... */
}
void update(int P, int Q, long long K) {
segm.upd(0, r - 1, segm.rt, P, Q, K);
/* ... */
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
return segm.qr(0, r - 1, segm.rt, P, U, Q, V);
}
