#include <bits/stdc++.h>
#include "game.h"
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void pankov(){
exit(0);
}
int n, m;
int type;
ll tree[103][400003];
ll tree2[8003][8003];
void update_tree(int v, int l, int r, int i, int pos, ll val){
if(l == r){
tree[i][v] = val;
return;
}
int mid = (l+r) >> 1;
if(pos <= mid) update_tree(v<<1, l, mid, i, pos, val);
else update_tree((v<<1)+1, mid+1, r, i, pos, val);
tree[i][v] = gcd2(tree[i][v<<1], tree[i][(v<<1)+1]);
}
ll get(int v, int l, int r, int i, int ql, int qr){
if(l > qr || ql > r) return 0;
if(ql <= l && r <= qr) return tree[i][v];
int mid = (l+r) >> 1;
return gcd2(get(v<<1, l, mid, i, ql, qr), get((v<<1)+1, mid+1, r, i, ql, qr));
}
void update_tree3(int v, int l, int r, int i, int pos, ll val){
if(l == r){
tree2[i][v] = val;
return ;
}
int mid = (l+r) >> 1;
if(pos <= mid) update_tree3(v<<1, l, mid, i, pos, val);
else update_tree3((v<<1)+1, mid+1, r, i, pos, val);
tree2[i][v] = gcd2(tree2[i][v<<1], tree2[i][(v<<1)+1]);
}
void update_tree2(int v, int l, int r, int i, int pos, ll val){
if(l == r){
update_tree3(1, 1, m, v, pos, val);
return;
}
int mid = (l+r) >> 1;
if(i <= mid) update_tree2(v<<1, l, mid, i, pos, val);
else update_tree2((v<<1)+1, mid+1, r, i, pos, val);
for(int j = 0; j < 8003; j++) tree2[v][j] = gcd2(tree2[v<<1][j], tree2[(v<<1)+1][j]);
}
ll get3(int v, int l, int r, int i, int ql, int qr){
if(l > qr || ql > r) return 0;
if(ql <= l && r <= qr) return tree2[i][v];
int mid = (l+r) >> 1;
return gcd2(get3(v<<1, l, mid, i, ql, qr), get3((v<<1)+1, mid+1, r, i, ql, qr));
}
ll get2(int v, int l, int r, int ql, int qr, int y1, int y2){
if(l > qr || ql > r) return 0;
if(ql <= l && r <= qr) return get3(1, 1, m, v, y1, y2);
int mid = (l+r) >> 1;
return gcd2(get2(v<<1, l, mid, ql, qr, y1, y2), get2((v<<1)+1, mid+1, r, ql, qr, y1, y2));
}
void init(int r, int c) {
n = r, m = c;
if(n <= 2000 && m <= 2000) type = 2;
else if(n <= 100 && m <= 100000) type = 1;
else pankov();
}
void update(int P, int Q, ll K) {
P++, Q++;
if(type == 1)
update_tree(1, 1, m, P, Q, K);
else
update_tree2(1, 1, n, P, Q, K);
}
ll calculate(int x1, int y1, int x2, int y2) {
x1++, y1++, x2++, y2++;
if(type == 1){
ll ans = 0;
for(int i = x1; i <= x2; i++){
ans = gcd2(ans, get(1, 1, m, i, y1, y2));
}
return ans;
}
else{
return get2(1, 1, n, x1, x2, y1, y2);
}
}
