#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int R, C, Q;
struct node1d{
ll val=0;
int pos=-1;
node1d *lc=nullptr, *rc=nullptr;
void update(int s, int e, int t, ll v){
if (e < t || t < s) return;
if (s == e){
val = v;
return;
}
int mid = (s+e)/2;
if (pos>=0){
if (pos <= mid){
lc = new node1d;
lc->pos = pos, lc->val = val;
}
else{
rc = new node1d;
rc->pos = pos, rc->val = val;
}
pos=-1;
}
if (t <= mid){
if (lc == nullptr){
lc = new node1d;
lc->pos = t, lc->val = v;
}
else lc->update(s, mid, t, v);
}
else{
if (rc == nullptr){
rc = new node1d;
rc->pos = t, rc->val = v;
}
else rc->update(mid+1, e, t, v);
}
val = 0;
if (lc != nullptr) val = __gcd(val, lc->val);
if (rc != nullptr) val = __gcd(val, rc->val);
}
ll query(int s, int e, int ts, int te){
if (te < s || e < ts) return 0;
if (ts <= s && e <= te) return val;
if (pos>=0){
if (ts <= pos && pos <= te) return val;
return 0;
}
int mid = (s+e)/2;
ll ret = 0;
if (lc != nullptr) ret = __gcd(ret, lc->query(s, mid, ts, te));
if (rc != nullptr) ret = __gcd(ret, rc->query(mid+1, e, ts, te));
return ret;
}
};
struct node2d{
node1d *T = new node1d;
node2d *lc=nullptr, *rc=nullptr;
void update(int s, int e, int tx, int ty, ll v){
if (e < tx || tx < s) return;
if (s == e){
T->update(0, C-1, ty, v);
return;
}
int mid = (s+e)/2;
if (tx <= mid){
if (lc == nullptr) lc = new node2d;
lc->update(s, mid, tx, ty, v);
}
else{
if (rc == nullptr) rc = new node2d;
rc->update(mid+1, e, tx, ty, v);
}
ll ret = 0;
if (lc != nullptr) ret = __gcd(ret, lc->T->query(0, C-1, ty, ty));
if (rc != nullptr) ret = __gcd(ret, rc->T->query(0, C-1, ty, ty));
T->update(0, C-1, ty, ret);
}
ll query(int s, int e, int txs, int txe, int tys, int tye){
if (txe < s || e < txs) return 0;
if (txs <= s && e <= txe) return T->query(0, C-1, tys, tye);
int mid = (s+e)/2;
ll ret = 0;
if (lc != nullptr) ret = __gcd(ret, lc->query(s, mid, txs, txe, tys, tye));
if (rc != nullptr) ret = __gcd(ret, rc->query(mid+1, e, txs, txe, tys, tye));
return ret;
}
} *Seg = new node2d;
void init(int r, int c){
R=r, C=c;
}
void update(int x, int y, ll v){
Seg->update(0, R-1, x, y, v);
}
ll calculate(int x1, int y1, int x2, int y2){
return Seg->query(0, R-1, x1, x2, y1, y2);
}
