#include "game.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
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;
}
int n;
vector < vector <long long> > t;
void upd(int tp, int pos, long long val, int v = 1, int tl = 1, int tr = n){
if(tl == tr)
t[tp][v] = val;
else {
int tm = (tl + tr) >> 1;
if(pos <= tm)
upd(tp, pos, val, v << 1, tl, tm);
else
upd(tp, pos, val, v << 1 | 1, tm + 1, tr);
t[tp][v] = gcd2(t[tp][v << 1], t[tp][v << 1 | 1]);
}
}
long long get(int tp, int l, int r, int v = 1, int tl = 1, int tr = n){
if(l > tr || tl > r)
return 0ll;
if(l <= tl && tr <= r)
return t[tp][v];
int tm = (tl + tr) >> 1;
return gcd2(get(tp, l, r, v << 1, tl, tm), get(tp, l, r, v << 1 | 1, tm + 1, tr));
}
void init(int R, int C) {
t.resize(R);
n = C;
for(int i = 0; i < R; i ++)
t[i].resize(4 * (C + 1));
}
void update(int P, int Q, long long K) {
upd(P, Q + 1, K);
}
long long calculate(int P, int Q, int U, int V) {
long long ans = 0;
for(int i = P; i <= U; i ++)
ans = gcd2(ans, get(i, Q + 1, V + 1));
return ans;
}
