#include "game.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
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 Node {
typedef long long T;
static constexpr T unit = 0;
T f(T a, T b) { return gcd2(a, b); }
Node *l = 0, *r = 0;
int lo, hi;
T val = unit;
//Lazy variables
// T mset = -unit;
// T madd = 0;
//Multi-dimensional variables
Node *N;
static int LO2;
static int HI2;
Node(int lo,int hi):lo(lo),hi(hi){} // Large interval of unit
/*
Node(vector<T>& v, int lo, int hi) : lo(lo), hi(hi) {
if (lo + 1 < hi) {
int mid = lo + (hi - lo)/2;
l = new Node(v, lo, mid); r = new Node(v, mid, hi);
val = f(l->val, r->val);
}
else val = v[lo];
}
*/
//Multi-dimensional initialization
Node(int lo1, int hi1, int lo2, int hi2) : lo(lo1), hi(hi1) {
N = new Node(lo2, hi2);
}
T query(int L, int R) {
if (R <= lo || hi <= L) return unit;
if (L <= lo && hi <= R) return val;
push();
return f(l->query(L, R), r->query(L, R));
}
//Multi-dimensional query
T query(int L1, int R1, int L2, int R2) {
if (R1 <= lo || hi <= L1) return unit;
if (L1 <= lo && hi <= R1) return N->query(L2, R2);
push();
return f(l->query(L1, R1, L2, R2), r->query(L1, R1, L2, R2));
}
void update_single(int X, T v) {
if (X < lo || hi <= X) return;
if (lo == X && hi == X+1) {
val = v;
return;
}
push();
l->update_single(X, v);
r->update_single(X, v);
val = f(l->val, r->val);
}
void update_multiple(int X, Node* _l, Node* _r) {
if (X < lo || hi <= X) return;
if (lo == X && hi == X+1) {
val = f(_l->N->query(X, X+1), _r->N->query(X, X+1));
return;
}
push();
l->update_multiple(X, _l, _r);
r->update_multiple(X, _l, _r);
val = f(l->val, r->val);
}
void update(int X, int Y, T v) {
if (X < lo || hi <= X) return;
if (lo == X && hi == X+1) {
N->update_single(Y, v);
return;
}
push();
l->update(X, Y, v);
r->update(X, Y, v);
N->update_multiple(Y, l, r);
}
void push() {
if (!l) {
int mid = lo + (hi - lo)/2;
//Multi-dimensional:
if (N) {l = new Node(lo, mid, LO2, HI2); r = new Node(mid, hi, LO2, HI2);}
else { l = new Node(lo, mid); r = new Node(mid, hi);}
}
//Range Add Functions
/*
if (mset != inf)
l->set(lo,hi,mset), r->set(lo,hi,mset), mset = inf;
else if (madd)
l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
*/
}
//Range Add Functions
/*
void set(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) mset = val = x, madd = 0;
else {
push(), l->set(L, R, x), r->set(L, R, x);
val = f(l->val, r->val);
}
}
void add(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
if (mset != inf) mset += x;
else madd += x;
val += x;
}
else {
push(), l->add(L, R, x), r->add(L, R, x);
val = f(l->val, r->val);
}
}
*/
};
int Node::LO2 = 0;
int Node::HI2 = 1e9;
Node* tree;
void init(int R, int C) {
//cerr << "init(" << R << ", " << C << ")" << endl;
Node::LO2 = 0;
Node::HI2 = C;
tree = new Node(0, R, 0, C);
}
void update(int P, int Q, long long K) {
//cerr << "update(" << P << ", " << Q << ", " << K << ")" << endl;
tree->update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
//cerr << "calculate(" << P << ", " << Q << ", " << U << ", " << V << ")" << endl;
return tree->query(P, U+1, Q, V+1);
}
