#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 10000, M = 1e5+10, K = 52, MX = 30;
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;
}
struct Node{
Node *L=nullptr, *R=nullptr;
int key; int Y; ll val, ans=0ll;
Node() : Y(rand()), key(0), val(0ll) {}
Node(int key): key(key), Y(rand()), val(0ll) {}
Node(int key, ll val): key(key), Y(rand()), val(val), ans(val) {}
};
typedef Node* Nodep;
void upd_val(Nodep v){
if(!v) return;
v->ans = v->val;
if(v->L) v->ans = gcd2(v->ans, v->L->ans);
if(v->R) v->ans = gcd2(v->ans, v->R->ans);
}
pair<Nodep, Nodep> split(Nodep v, int pos){
if(!v) return {v, v};
if(v->key >= pos){
auto p = split(v->L, pos);
v->L = p.ss;
upd_val(v);
return {p.ff, v};
}else{
auto p = split(v->R, pos);
v->R = p.ff;
upd_val(v);
return {v, p.ss};
}
}
Nodep merge(Nodep l, Nodep r){
if(!l || !r){
return l ? l : r;
}
if(l->Y > r->Y){
auto p = merge(l->R, r);
l->R = p;
upd_val(l);
return l;
}else{
auto p = merge(l, r->L);
r->L = p;
upd_val(r);
return r;
}
}
map<int, Node*> T;
map<pii, ll> VAL;
// ll T[8005][8005];
int n, m;
void init(int R, int C) {
n = R;
m = C;
// for(int i = 0; i <= 4*n; ++i){
// for(int j = 0; j <= 4*m; ++j) T[i][j] = 0;
// }
}
ll get_val(pii x){
if(VAL.find(x) == VAL.end())
return 0;
return VAL[x];
}
Nodep get(int x){
if(T.find(x) == T.end()){
T[x] = nullptr;
}
return T[x];
}
Nodep updY(Nodep v, int P, int lx, int rx, ll val, int k){
if(lx == rx){
auto p = split(v, P);
auto p2 = split(p.ss, P + 1);
if(!p2.ff){
auto t = new Node(P, val);
p.ss = merge(p2.ff, p2.ss);
p.ff = merge(p.ff, t);
}else{
p2.ff->key = p2.ff->ans = val;
p.ss = merge(p2.ff, p2.ss);
}
v = merge(p.ff, p.ss);
VAL[pii{k, P}] = val;
// cout << v->ans << '\n';
}else{
auto p = split(v, P);
auto p2 = split(p.ss, P + 1);
if(!p2.ff){
auto t = new Node(P, gcd2(get_val(pii{k<<1, P}), get_val(pii{k<<1|1, P})));
p.ss = merge(p2.ff, p2.ss);
p.ff = merge(p.ff, t);
}else{
p2.ff->key = p2.ff->ans = gcd2(get_val(pii{k<<1, P}), get_val(pii{k<<1|1, P}));
p.ss = merge(p2.ff, p2.ss);
}
v = merge(p.ff, p.ss);
// cout << v->ans << '\n';
}
// if(l == r){
// if(lx == rx){
// T[{kx, k}] = val;
// }else{
// T[{kx, k}] = gcd2(get(pii{kx<<1, k}), get(pii{kx<<1|1, k}));
// }
// }else{
// int m = l+r>>1;
// if(p <= m) updY(l, m, p, lx, rx, k<<1, kx, val);
// else updY(m+1, r, p, lx, rx, k<<1|1, kx, val);
// T[{kx, k}] = gcd2(get(pii{kx, k<<1}), get(pii{kx, k<<1|1}));
// }
return v;
}
void updX(int l, int r, int p, int k, int y, ll val){
if(l != r){
int m = l+r>>1;
if(p <= m) updX(l, m, p, k<<1, y, val);
else updX(m+1, r, p, k<<1|1, y, val);
}
T[k] = updY(get(k), y, l, r, val, k);
}
void update(int P, int Q, long long K) {
++P, ++Q;
// cout << P << ' ' << Q << ' ' << K << '\n';
updX(1, n, P, 1, Q, K);
// cout << "f\n";
}
ll getY(Nodep v, int l, int r){
if(!v) return 0ll;
auto p = split(v, l);
auto p2 = split(p.ss, r + 1);
ll ans;
if(!p2.ff){
ans = 0ll;
}else ans = p2.ff->ans;
p.ss = merge(p2.ff, p2.ss);
v = merge(p.ff, p.ss);
return ans;
// if(ly > r || l > ry) return 0ll;
// if(ly <= l && r <= ry){
// return get(pii{kx, k});
// }
// int m = l+r>>1;
// return gcd2(getY(l, m, ly, ry, k<<1, kx), getY(m + 1, r, ly, ry, k<<1|1, kx));
}
ll getX(int l, int r, int lx, int rx, int k, int ly, int ry){
if(lx > r || l > rx) return 0ll;
if(lx <= l && r <= rx){
return getY(get(k), ly, ry);
}
int m = l+r>>1;
return gcd2(getX(l, m, lx, rx, k<<1, ly, ry), getX(m+1, r, lx, rx, k<<1|1, ly, ry));
}
long long calculate(int P, int Q, int U, int V) {
++P, ++Q, ++U, ++V;
return getX(1, n, P, U, 1, Q, V);
}
