#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;
}
int rnd() { return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15)); }
struct Node{
Node *L, *R;
int key; int Y; ll val, ans=0ll;
Node() : Y(rand()), key(0), val(0ll), L(nullptr), R(nullptr) {}
Node(int key): key(key), Y(rnd()), val(0ll), L(nullptr), R(nullptr) {}
Node(int key, ll val): key(key), Y(rnd()), val(val), ans(val), L(nullptr), R(nullptr) {}
};
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 ? r : l;
}
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;
int n, m;
void init(int R, int C) {
n = R;
m = C;
}
ll get_val(pii x){
if(VAL.find(x) == VAL.end())
return 0ll;
return VAL[x];
}
Nodep get(int x){
if(T.find(x) == T.end()){
T[x] = nullptr;
}
return T[x];
}
int getto(Nodep v){
if(!v) return 0ll;
return v->key;
}
void updY(int P, int lx, int rx, ll val, int k){
Nodep v = get(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);
p2.ff = merge(p2.ff, t);
p.ss = merge(p2.ff, p2.ss);
}else{
p2.ff->val = p2.ff->ans = val;
p.ss = merge(p2.ff, p2.ss);
}
v = merge(p.ff, p.ss);
VAL[pii{k, P}] = val;
}else{
auto p = split(v, P);
auto p2 = split(p.ss, P + 1);
ll new_val = gcd2(get_val(pii{k<<1, P}), get_val(pii{k<<1|1, P}));
if(!p2.ff){
auto t = new Node(P, new_val);
p2.ff = merge(p2.ff, t);
p.ss = merge(p2.ff, p2.ss);
}else{
p2.ff->val = p2.ff->ans = new_val;
p.ss = merge(p2.ff, p2.ss);
}
v = merge(p.ff, p.ss);
VAL[pii{k, P}] = new_val;
}
T[k] = 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);
}
updY(y, l, r, val, k);
}
void update(int P, int Q, long long K) {
++P, ++Q;
updX(1, n, P, 1, Q, K);
}
ll getY(Nodep v, int l, int r){
if(v == nullptr) 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;
}
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);
}
