#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cout << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 3e5 + 10;
vector<ll> seg[maxn << 2];
vector<pll> val[maxn << 2];
void build(vector<ll> &seg, vector<pll> &val, int v, int l, int r){
if (l + 1 == r){
seg[v] = val[l].S;
return;
}
int mid = (l + r) >> 1;
int lc = v << 1;
int rc = lc | 1;
build(seg, val, lc, l, mid);
build(seg, val, rc, mid, r);
seg[v] = gcd(seg[lc], seg[rc]);
}
void change(vector<ll> &seg, int v, int l, int r, int idx, ll val){
if (idx < l || r <= idx) return;
if (l + 1 == r){
seg[v] = val;
return;
}
int mid = (l + r) >> 1;
int lc = v << 1;
int rc = lc | 1;
change(seg, lc, l, mid, idx, val);
change(seg, rc, mid, r, idx, val);
seg[v] = gcd(seg[lc], seg[rc]);
}
ll get(vector<ll> &seg, int v, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return seg[v];
int mid = (l + r) >> 1;
int lc = v << 1;
int rc = lc | 1;
return gcd(get(seg, lc, l, mid, ql, qr),
get(seg, rc, mid, r, ql, qr));
}
vector<pll> num[maxn];
void d2build(int v, int l, int r){
val[v].clear();
if (l + 1 == r){
for (auto x: num[l]) val[v].push_back(x);
}
else{
int mid = (l + r) >> 1;
int lc = v << 1;
int rc = lc | 1;
d2build(lc, l, mid);
d2build(rc, mid, r);
int ptl = 0, ptr = 0;
while(ptl < val[lc].size() || ptr < val[rc].size()){
if (ptr == val[rc].size() || (ptl < val[lc].size() && val[lc][ptl] < val[rc][ptr])){
val[v].push_back(val[lc][ptl]);
ptl++;
}
else{
val[v].push_back(val[rc][ptr]);
ptr++;
}
}
}
seg[v].resize(4 * val[v].size() + 1);
build(seg[v], val[v], 1, 0, val[v].size());
}
void d2change(int v, int l, int r, int idx, ll ptr, ll prval, ll nwval){
if (idx < l || r <= idx) return;
int idx2 = lower_bound(all(val[v]), MP(ptr, prval)) - val[v].begin();
val[v][idx2].S = nwval;
change(seg[v], 1, 0, val[v].size(), idx2, nwval);
if (l + 1 == r) return;
int mid = (l + r) >> 1;
int lc = v << 1;
int rc = lc | 1;
d2change(lc, l, mid, idx, ptr, prval, nwval);
d2change(rc, mid, r, idx, ptr, prval, nwval);
}
ll d2get(int v, int l, int r, int qu, int qd, ll ql, ll qr){
if (qd <= l || r <= qu) return 0;
if (qu <= l && r <= qd){
int L = lower_bound(all(val[v]), MP(ql, 0ll)) - val[v].begin();
int R = lower_bound(all(val[v]), MP(qr, 0ll)) - val[v].begin();
return get(seg[v], 1, 0, val[v].size(), L, R);
}
int mid = (l + r) >> 1;
int lc = v << 1;
int rc = lc | 1;
return gcd(d2get(lc, l, mid, qu, qd, ql, qr),
d2get(rc, mid, r, qu, qd, ql, qr));
}
const int sq = 1200;
vector<pair<pii,ll>> p1, p2;
vector<int> numx;
void init(int R, int C) {
// ok :/
}
void reset(){
for (int i = 0; i < numx.size(); i++) num[i].clear();
numx.clear();
for (auto x: p2) p1.push_back(x);
sort(all(p1));
p2.clear();
int ptr = 0;
numx.push_back(p1[0].F.F);
num[0].push_back(MP(p1[0].F.S, p1[0].S));
for (int i = 1; i < p1.size(); i++){
if (p1[i].F.F != p1[i-1].F.F){
ptr++;
numx.push_back(p1[i].F.F);
}
num[ptr].push_back(MP(p1[i].F.S, p1[i].S));
}
d2build(1, 0, numx.size());
}
void update(int P, int Q, long long K) {
int idx = lower_bound(all(p1), MP(MP(P,Q), 0ll)) - p1.begin();
if (idx != p1.size() && p1[idx].F == MP(P,Q)){
int idx2 = lower_bound(all(numx), P) - numx.begin();
d2change(1, 0, numx.size(), idx2, Q, p1[idx].S, K);
p1[idx].S = K;
return;
}
for (int i = 0; i < p2.size(); i++){
if (p2[i].F == MP(P, Q)){
p2[i].S = K;
return;
}
}
p2.push_back(MP(MP(P, Q), K));
if (p2.size() == sq) reset();
}
long long calculate(int P, int Q, int U, int V) {
int l = lower_bound(all(numx), P) - numx.begin();
int r = lower_bound(all(numx), U+1) - numx.begin();
ll res = d2get(1, 0, numx.size(), l, r, Q, V+1);
for (auto [x, y]: p2){
if (P <= x.F && x.F <= U && Q <= x.S && x.S <= V) res = gcd(res, y);
}
return res;
}
