#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
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;
}
vector<vector<ll>> st;
int lenx = 1, leny = 1;
ll comb(ll a, ll b){
if(!a) return b;
if(!b) return a;
return gcd2(a, b);
}
ll qry_y(int l, int r, int ix, int i = 1, int s = 0, int e = leny){
if(l >= e || r <= s) return 0;
if(l <= s && e <= r){
return st[ix][i];
}
return comb(qry_y(l, r, ix, i * 2, s, (s + e) / 2),
qry_y(l, r, ix, i * 2 + 1, (s + e) / 2, e));
}
ll qry_x(int l, int ly, int r, int ry, int i = 1, int s = 0, int e = lenx){
if(l >= e || r <= s) return 0;
if(l <= s && e <= r){
return qry_y(ly, ry, i);
}
return comb(qry_x(l, ly, r, ry, i * 2, s, (s + e) / 2),
qry_x(l, ly, r, ry, i * 2 + 1, (s + e) / 2, e));
}
void upd_y(int x, int y, ll val, bool b, int ix, int i = 1, int s = 0, int e = leny){
if(y >= e || y < s) return;
if(y == s && s + 1 == e){
if(b) st[ix][i] = val;
else st[ix][i] = comb(st[ix * 2][i], st[ix * 2 + 1][i]);
return;
}
upd_y(x, y, val, b, ix, i * 2, s, (s + e) / 2);
upd_y(x, y, val, b, ix, i * 2 + 1, (s + e) / 2, e);
st[ix][i] = comb(st[ix][i * 2], st[ix][i * 2 + 1]);
}
void upd_x(int x, int y, ll val, int i = 1, int s = 0, int e = lenx){
if(x >= e || x < s) return;
if(x == s && s + 1 == e) {
upd_y(x, y, val, true, i);
return;
}
upd_x(x, y, val, i * 2, s, (s + e) / 2);
upd_x(x, y, val, i * 2 + 1, (s + e) / 2, e);
upd_y(x, y, val, false, i);
}
void init(int R, int C) {
while(lenx < R) lenx *= 2;
while(leny < C) leny *= 2;
st.resize(2 * lenx, vector<ll>(2 * leny, 0));
}
void update(int P, int Q, long long K) {
upd_x(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return qry_x(P, Q, U + 1, V + 1);
}
