// ~ 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 = 2e7;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int tt = 0;
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;
}
namespace seg{
int n, m, newnode = 2, innernode = 2, inner[maxnt];
int chil[maxnt][2], innerchil[maxnt][2];
ll g[maxnt];
void innerupdbase(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] = val;
return;
}
int mid = (l + r) >> 1;
if(id < mid){
if(!innerchil[v][0])
innerchil[v][0] = innernode++;
innerupdbase(l, mid, id, val, innerchil[v][0]);
}
else{
if(!innerchil[v][1])
innerchil[v][1] = innernode++;
innerupdbase(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;
}
void innerupdult(int l, int r, int id, int v1, int v2, int v3){
g[v1] = gcd2(g[v2], g[v3]);
if(r - l == 1)
return;
int mid = (l + r) >> 1;
if(id < mid){
if(!innerchil[v1][0])
innerchil[v1][0] = innernode++;
innerupdult(l, mid, id, innerchil[v1][0], innerchil[v2][0], innerchil[v3][0]);
}
else{
if(!innerchil[v1][1])
innerchil[v1][1] = innernode++;
innerupdult(mid, r, id, innerchil[v1][1], innerchil[v2][1], innerchil[v3][1]);
}
}
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;
if(r - l == 1){
innerupdbase(0, m, id2, val, inner[v]);
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]);
}
innerupdult(0, m, id2, inner[v], inner[chil[v][0]], inner[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]));
}
inline void clear(int nn, int mm){
n = nn;
m = mm;
for(int i = 0; i < newnode; i++)
inner[i] = chil[i][0] = chil[i][1] = 0;
for(int i = 0; i < innernode; i++)
innerchil[i][0] = innerchil[i][1] = g[i] = 0;
newnode = innernode = 2;
}
}
int szx, szy, n, m;
int newnode = 2, innernode = 2, inner[maxnt];
int chil[maxnt][2], innerchil[maxnt][2];
ll g[maxnt];
vector <int> avx, avy;
map <pair<int, int>, ll> av;
set <pair<int, int>> avseg;
void innerupdbase(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] = val;
return;
}
int mid = (l + r) >> 1;
if(id < mid){
if(!innerchil[v][0])
innerchil[v][0] = innernode++;
innerupdbase(l, mid, id, val, innerchil[v][0]);
}
else{
if(!innerchil[v][1])
innerchil[v][1] = innernode++;
innerupdbase(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;
}
void innerupdult(int l, int r, int id, int v1, int v2, int v3){
g[v1] = gcd2(g[v2], g[v3]);
if(r - l == 1)
return;
int mid = (l + r) >> 1;
if(id < mid){
if(!innerchil[v1][0])
innerchil[v1][0] = innernode++;
innerupdult(l, mid, id, innerchil[v1][0], innerchil[v2][0], innerchil[v3][0]);
}
else{
if(!innerchil[v1][1])
innerchil[v1][1] = innernode++;
innerupdult(mid, r, id, innerchil[v1][1], innerchil[v2][1], innerchil[v3][1]);
}
}
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;
if(r - l == 1){
innerupdbase(0, m, id2, val, inner[v]);
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]);
}
innerupdult(0, m, id2, inner[v], inner[chil[v][0]], inner[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;
/* ... */
}
inline void rebuild(){
sort(all(avx));
sort(all(avy));
avx.resize(unique(all(avx)) - avx.begin());
avy.resize(unique(all(avy)) - avy.begin());
szx = avx.size();
szy = avy.size();
for(int i = 0; i < newnode; i++)
inner[i] = chil[i][0] = chil[i][1] = 0;
for(int i = 0; i < innernode; i++)
innerchil[i][0] = innerchil[i][1] = g[i] = 0;
newnode = innernode = 2;
seg::clear(szx, szy);
for(auto it = av.begin(); it != av.end(); it++){
avseg.insert(it->fi);
int ptx = lower_bound(avx.begin(), avx.begin() + szx, (it->fi).fi) - avx.begin();
int pty = lower_bound(avy.begin(), avy.begin() + szy, (it->fi).se) - avy.begin();
seg::upd(0, szx, ptx, pty, it->se, 1);
}
}
int opt = 0;
void update(int x, int y, long long k) {
opt++;
if(newnode > 5e6 || innernode > 5e6)
rebuild();
if(avseg.find(mp(x, y)) != avseg.end()){
av[{x, y}] = k;
x = lower_bound(avx.begin(), avx.begin() + szx, x) - avx.begin();
y = lower_bound(avy.begin(), avy.begin() + szy, y) - avy.begin();
seg::upd(0, szx, x, y, k, 1);
return;
}
upd(0, n, x, y, k, 1);
av[{x, y}] = k;
avx.pb(x);
avy.pb(y);
}
long long calculate(int l, int d, int r, int u) {
tt++;
ll ans = get(0, n, l, r + 1, d, u + 1, 1);
//if(tt == 129048)
// cerr << l << ' ' << r << ' ' << d << ' ' << u << endl;
l = lower_bound(avx.begin(), avx.begin() + szx, l) - avx.begin();
r = upper_bound(avx.begin(), avx.begin() + szx, r) - avx.begin();
d = lower_bound(avy.begin(), avy.begin() + szy, d) - avy.begin();
u = upper_bound(avy.begin(), avy.begin() + szy, u) - avy.begin();
ans = gcd2(ans, seg::get(0, szx, l, r, d, u, 1));
//if(tt == 129048)
// cerr << newnode << ' ' << innernode << ' ' << ans << ' ' << opt << ' ' << l << ' ' << r << ' ' << d << ' ' << u << endl;
return ans;
}
