#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 8005, M = 1e5+10, MX = 30;
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<ll> T[N][N];
int n, m;
void init(int R, int C) {
n = R;
m = C;
// for(int i = 0; i <= 4*n; ++i){
// for(int j = 0; j <= 4*m; ++j) T[i][j] = 0;
// }
}
ll get(vector<ll> &v){
if(v.empty()) return 0ll;
return v[0];
}
void upd(vector<ll> &v, ll val){
if(v.empty()) v.pb(val);
else v[0] = val;
}
ll gcd3(vector<ll> &x, vector<ll> &y){
return gcd2(get(x), get(y));
}
void updY(int l, int r, int p, int lx, int rx, int k, int kx, ll val){
if(l == r){
if(lx == rx){
upd(T[kx][k], val);
}else{
upd(T[kx][k], gcd3(T[kx<<1][k], T[kx<<1|1][k]));
}
}else{
int m = l+r>>1;
if(p <= m) updY(l, m, p, lx, rx, k<<1, kx, val);
else updY(m+1, r, p, lx, rx, k<<1|1, kx, val);
upd(T[kx][k], gcd3(T[kx][k<<1], T[kx][k<<1|1]));
}
}
void updX(int l, int r, int p, int k, int y, ll val){
if(l != r){
int m = l+r>>1;
if(p <= m) updX(l, m, p, k<<1, y, val);
else updX(m+1, r, p, k<<1|1, y, val);
}
updY(1, m, y, l, r, 1, k, val);
}
void update(int P, int Q, long long K) {
++P, ++Q;
updX(1, n, P, 1, Q, K);
}
ll getY(int l, int r, int ly, int ry, int k, int kx){
if(ly > r || l > ry) return 0ll;
if(ly <= l && r <= ry){
return get(T[kx][k]);
}
int m = l+r>>1;
return gcd2(getY(l, m, ly, ry, k<<1, kx), getY(m + 1, r, ly, ry, k<<1|1, kx));
}
ll getX(int l, int r, int lx, int rx, int k, int ly, int ry){
if(lx > r || l > rx) return 0ll;
if(lx <= l && r <= rx){
return getY(1, m, ly, ry, 1, k);
}
int m = l+r>>1;
return gcd2(getX(l, m, lx, rx, k<<1, ly, ry), getX(m+1, r, lx, rx, k<<1|1, ly, ry));
}
long long calculate(int P, int Q, int U, int V) {
++P, ++Q, ++U, ++V;
return getX(1, n, P, U, 1, Q, V);
}
