#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
typedef vector<ll> vl;
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 segtree1 {
struct node1 {
ll fr, to;
ll val;
node1 * leCh;
node1 * riCh;
node1 (ll _fr, ll _to) {
fr = _fr;
to = _to;
val = 0;
leCh = riCh = nullptr;
}
void upd () {
ll mid = (fr+to)/2;
if (!leCh)
leCh = new node1 (fr, mid);
if (!riCh)
riCh = new node1 (mid+1, to);
}
};
void upd (ll p, ll newVal, node1 * cur) {
if (cur->fr == cur->to){
cur->val = newVal;
return;
}
ll mid = (cur->fr) + (cur->to);
mid /= 2;
cur->upd();
if (p <= mid)
upd(p, newVal, cur->leCh);
else
upd (p, newVal, cur->riCh);
cur->val = gcd2(cur->leCh->val, cur->riCh->val);
}
ll get(ll rfr, ll rto, node1 * cur) {
if (rfr > (cur->to) || rto < (cur->fr)) return 0;
if (rfr <= (cur->fr) && (cur->to) <= rto) return cur->val;
if (!(cur->leCh)) return 0;
cur->upd();
return gcd2(get(rfr, rto, cur->leCh), get(rfr, rto, cur->riCh));
}
node1 * root = new node1 (0, 1e9);
void upd (ll pos, ll newVal) {
upd(pos, newVal, root);
}
ll get (ll fr, ll to) {
return get(fr, to, root);
}
};
segtree1 tree[2100];
void init(int R, int C) {
}
void update(int P, int Q, long long K) {
tree[P].upd(Q, K);
}
long long calculate(int P, int Q, int U, int V) {
ll ans = 0;
FOR(i, P, U) {
//cout << " i = " << i << " q=" << Q << " v=" << V << " get= " << tree[i].get(Q,V) << endl;
ans = gcd2(ans, tree[i].get(Q, V));
}
return ans;
}
