#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 3e5 + 5;
typedef long long ll;
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 st{
int l, r;
vector<ll> t;
void init(int ll, int rr, int C){
l = ll;
r = rr;
t.resize(4*C, 0);
}
void upd(int v, int tl, int tr, int pos, ll val, vector<ll> &t1, vector<ll> &t2){
if(l == r){
if(tl == tr){
t[v] = val;
}else{
int tm = (tl + tr) / 2;
if(pos <= tm)
upd(2*v, tl, tm, pos, val, t1, t2);
else upd(2*v + 1, tm + 1, tr, pos, val, t1, t2);
t[v] = gcd2(t[2*v], t[2*v + 1]);
}
}else{
if(tl == tr){
t[v] = gcd2(t1[v], t2[v]);
}else{
int tm = (tl + tr) / 2;
if(pos <= tm)
upd(2*v, tl, tm, pos, val, t1, t2);
else upd(2*v + 1, tm + 1, tr, pos, val, t1, t2);
t[v] = gcd2(t1[v], t2[v]);
}
}
}
ll que(int v, int tl, int tr, int l, int r){
if(l > r) return -1;
else if(tl == l && tr == r){
return t[v];
}else{
int tm = (tl + tr) / 2;
ll ans1 = que(2*v, tl, tm, l, min(tm ,r)), ans2 = que(2*v + 1, tm + 1, tr, max(tm + 1, l), r);
if(ans1 == -1) return ans2;
else if(ans2 == -1) return ans1;
else return gcd2(ans1, ans2);
}
}
} t[4*MAXN];
int c, r;
void build(int v, int tl, int tr){
if(tl == tr){
t[v].init(tl, tr, c);
}else{
int tm = (tl + tr) / 2;
build(2*v, tl, tm);
build(2*v+1, tm + 1, tr);
t[v].init(tl, tr, c);
}
}
void upd(int v, int tl, int tr, int posX, int posY, ll val){
if(tl == tr){
t[v].upd(1, 0, c - 1, posY, val, t[v].t, t[v].t);
}else{
int tm = (tl + tr) / 2;
if(posX <= tm) upd(2*v, tl, tm, posX, posY, val);
else upd(2*v+1, tm + 1, tr, posX, posY, val);
t[v].upd(1, 0, c - 1, posY, val, t[2*v].t, t[2*v + 1].t);
}
}
ll que(int v, int tl, int tr, int l1, int r1, int l2, int r2){
if(l1 > r1) return -1;
else if(tl == l1 && tr == r1){
return t[v].que(1, 0, c - 1, l2, r2);
}else{
int tm = (tl + tr) / 2;
ll ans1 = que(2*v, tl, tm, l1, min(tm, r1), l2, r2), ans2 = que(2*v + 1, tm + 1, tr, max(tm + 1, l1), r1, l2, r2);
if(ans1 == -1) return ans2;
else if(ans2 == -1) return ans1;
else return gcd2(ans1, ans2);
}
}
void init(int R, int C) {
c = C;
r = R;
build(1, 0, R - 1);
}
void update(int P, int Q, long long K) {
upd(1, 0, r - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return que(1, 0, r - 1, P, U, Q, V);
}
