#include <bits/stdc++.h>
#include "game.h"
#define pii pair<int, int>
#define pb push_back
#define gcd __gcd
#define endl "\n"
#define task "CX"
using namespace std;
const int N = 2e3 + 5;
typedef long long ll;
int n, m, q, seg[4 * N][4 * N];
void updy(ll idx, ll idy, ll lx, ll rx, ll ly, ll ry, ll i, ll j, ll val){
if(ly == ry){
if(lx == rx) seg[idx][idy] = val;
else seg[idx][idy] = gcd(seg[idx * 2][idy], seg[idx * 2 + 1][idy]);
}
else{
ll my = (ly + ry) / 2;
if(j <= my) updy(idx, idy * 2, lx, rx, ly, my, i, j, val);
else updy(idx, idy * 2 + 1, lx, rx, my + 1, ry, i, j, val);
seg[idx][idy] = gcd(seg[idx][idy * 2], seg[idx][idy * 2 + 1]);
}
}
void updx(ll idx, ll tlx, ll trx, ll i, ll j, ll val){
if(tlx != trx){
ll mx = (tlx + trx) / 2;
if(i <= mx) updx(idx * 2, tlx, mx, i, j, val);
else updx(idx * 2 + 1, mx + 1, trx, i, j, val);
}
updy(idx, 1, tlx, trx, 1, m, i, j, val);
}
ll gety(ll idx, ll idy, ll tly, ll tri, ll ly, ll ry){
if(tri < ly || ry < tly) return 0;
if(ly <= tly && tri <= ry){ return seg[idx][idy]; }
ll my = (tly + tri) / 2;
return gcd(gety(idx, idy * 2, tly, my, ly, ry), gety(idx, idy * 2 + 1, my + 1, tri, ly, ry));
}
ll getx(ll idx, ll tlx, ll trx, ll lx, ll rx, ll ly, ll ry){
if(rx < tlx || trx < lx) return 0;
if(lx <= tlx && trx <= rx){ return gety(idx, 1, 1, m, ly, ry); }
ll mx = (tlx + trx) / 2;
return gcd(getx(idx * 2, tlx, mx, lx, rx, ly, ry), getx(idx * 2 + 1, mx + 1, trx, lx, rx, ly, ry));
}
void init(int R, int C){
n = R; m = C;
}
void update(int P, int Q, long long K){
++P; ++Q;
updx(1, 1, n, P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
++P; ++U; ++Q; ++V;
return getx(1, 1, n, P, U, Q, V);
}
