#include <bits/stdc++.h>
#include "game.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ii = pair<int, int>;
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
ll st[2001][2001];
int R, C;
void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, ll K) {
if(ly == ry) {
if(lx == rx)
st[vx][vy] = K;
else st[vx][vy] = __gcd(st[vx * 2][vy], st[vx * 2 + 1][vy]);
return;
}
int my = (ly + ry) / 2;
if(y <= my)
update_y(vx, lx, rx, vy * 2, ly, my, x, y, K);
else update_y(vx, lx, rx, vy * 2 + 1, my + 1, ry, x, y, K);
st[vx][vy] = __gcd(st[vx][vy * 2], st[vx][vy * 2 + 1]);
}
void update_x(int vx, int lx, int rx, int x, int y, ll K) {
if(lx != rx) {
int mx = (lx + rx) / 2;
if(x <= mx)
update_x(vx * 2, lx, mx, x, y, K);
else update_x(vx * 2 + 1, mx + 1, rx, x, y, K);
}
update_y(vx, lx, rx, 1, 0, C - 1, x, y, K);
}
int sum_y(int vx, int vy, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return -1;
if(l >= lo && r <= hi) return st[vx][vy];
int A = sum_y(vx, vy * 2, l, (l + r) / 2, lo, hi);
int B = sum_y(vx, vy * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
if(A == -1) return B;
if(B == -1) return A;
return __gcd(A, B);
}
int sum_x(int vx, int l, int r, int lf, int rf, int lo, int hi) {
if(l > rf || r < lf) return -1;
if(l >= lf && r <= rf)
return sum_y(vx, 1, 0, C - 1, lo, hi);
int A = sum_x(vx * 2, l, (l + r) / 2, lf, rf, lo, hi);
int B = sum_x(vx * 2 + 1, (l + r) / 2 + 1, r, lf, rf, lo, hi);
if(A == -1) return B;
if(B == -1) return A;
return __gcd(A, B);
}
void init(int N, int M) {
R = N; C = M;
}
void update(int P, int Q, ll K) {
update_x(1, 0, R - 1, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return sum_x(1, 0, R - 1, P, U, Q, V);
}
