// ~ Be Name Khoda ~ //
#include "game.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1e7;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int n, m, newnode = 2, innernode = 2, inner[maxnt];
int chil[maxnt][2], innerchil[maxnt][2];
ll g[maxnt];
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;
}
void innerupd(int l, int r, int id, ll val, int v){
//cout << "inner upd with " << l << ' ' << r << ' ' << id << ' ' << val << ' ' << v << endl;
if(r - l == 1){
g[v] = gcd2(g[v], val);
return;
}
int mid = (l + r) >> 1;
if(id < mid){
if(!innerchil[v][0])
innerchil[v][0] = innernode++;
innerupd(l, mid, id, val, innerchil[v][0]);
}
else{
if(!innerchil[v][1])
innerchil[v][1] = innernode++;
innerupd(mid, r, id, val, innerchil[v][1]);
}
g[v] = gcd2(g[innerchil[v][0]], g[innerchil[v][1]]);
//cout << "ok " << l << ' ' << r << ' ' << val << ' ' << v << ' ' << g[v] << ' ' << g[innerchil[v][1]] << ' ' << g[innerchil[v][0]] << endl;
}
ll innerget(int l, int r, int lq, int rq, int v){
if(v == 0 || rq <= l || r <= lq)
return 0;
if(lq <= l && r <= rq){
//cout << "inner getting " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << g[v] << endl;
return g[v];
}
int mid = (l + r) >> 1;
return gcd2(innerget(l, mid, lq, rq, innerchil[v][0]), innerget(mid, r, lq, rq, innerchil[v][1]));
}
void upd(int l, int r, int id, int id2, ll val, int v){
if(!inner[v])
inner[v] = innernode++;
//cout << "entering iiner update " << l << ' ' << r << ' ' << v << ' ' << inner[v] << ' ' << val << endl;
innerupd(0, m, id2, val, inner[v]);
if(r - l == 1)
return;
int mid = (l + r) >> 1;
if(id < mid){
if(!chil[v][0])
chil[v][0] = newnode++;
upd(l, mid, id, id2, val, chil[v][0]);
}
else{
if(!chil[v][1])
chil[v][1] = newnode++;
upd(mid, r, id, id2, val, chil[v][1]);
}
}
ll get(int l, int r, int lq, int rq, int llq, int rrq, int v){
if(v == 0 || rq <= l || r <= lq)
return 0;
if(lq <= l && r <= rq){
if(!inner[v])
return 0;
ll ret = innerget(0, m, llq, rrq, inner[v]);
//cout << "here " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << ret << endl;
return ret;
}
int mid = (l + r) >> 1;
return gcd2(get(l, mid, lq, rq, llq, rrq, chil[v][0]), get(mid, r, lq, rq, llq, rrq, chil[v][1]));
}
void init(int R, int C) {
n = R;
m = C;
/* ... */
}
void update(int x, int y, long long k) {
upd(0, n, x, y, k, 1);
}
long long calculate(int l, int d, int r, int u) {
return get(0, n, l, r + 1, d, u + 1, 1);
}
