#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int MM = 1e6;
mt19937 rng(42069);
struct INode{ // 28 bytes
int c[2];
pair<int,int> pos; // y,x
int64_t g,v; int pri;
INode(int p, int q, int64_t k){
pos = {q,p};
g = v = k;
pri = rng();
c[0] = c[1] = 0;
}
INode(){
pos = {0,0};
g = v = pri = 0;
c[0] = c[1] = 0;
}
}ibuf[MM]; int ibuf_pos;
int64_t gcd(int64_t a, int64_t b) {
if (!a || !b)
return a | b;
auto shift = __builtin_ctzll(a | b);
a >>= __builtin_ctzll(a);
do {
b >>= __builtin_ctzll(b);
if (a > b)
swap(a, b);
b -= a;
} while (b);
return a << shift;
}
void upd(int u){
auto& cur = ibuf[u];
cur.g = cur.v;
if(cur.c[0]) cur.g = gcd(cur.g,ibuf[cur.c[0]].g);
if(cur.c[1]) cur.g = gcd(cur.g,ibuf[cur.c[1]].g);
}
int alloc(int p, int q, int64_t k){
auto& cur = ibuf[++ibuf_pos];
//cout << "creating new node: " << pos << " " << k << "\n";
cur = INode(p,q,k);
return ibuf_pos;
}
array<int,2> split(int u, pair<int,int> q){
if(!u) return {0,0};
if(ibuf[u].pos >= q){
auto p = split(ibuf[u].c[0],q); ibuf[u].c[0] = p[1];
upd(u);
return {p[0],u};
} else{
auto p = split(ibuf[u].c[1],q); ibuf[u].c[1] = p[0];
upd(u);
return {u,p[1]};
}
}
int merge(int l, int r){
if(!l) return r;
if(!r) return l;
int u;
if(ibuf[l].pri > ibuf[r].pri) ibuf[l].c[1] = merge(ibuf[l].c[1],r),u = l;
else ibuf[r].c[0] = merge(l,ibuf[r].c[0]), u = r;
upd(u);
return u;
}
int ins(int rt, int p, int q, int64_t k){
auto[lft,tmp] = split(rt,{q,p});
auto[same,rit] = split(tmp,{q,p+1});
return merge(lft,merge(alloc(p,q,k),rit));
}
int64_t query_in(int& rt, int l, int r){
auto[lft,tmp] = split(rt,{l,0});
auto[in,rit] = split(tmp,{r+1,0});
auto ans = ibuf[in].g;
rt = merge(lft,merge(in,rit));
return ans;
}
struct Node{ // 16 bytes
int l,r; // index in buffer
int rt; // index in ibuf
}buf[MM*4];
int n,m,pos;
int alloc_out(){
Node& rt = buf[++pos];
rt.l = rt.r = 0; rt.rt = 0;
return pos;
}
void print(int u){
if(!u) return;
print(ibuf[u].c[0]);
cout << ibuf[u].v << " ";
print(ibuf[u].c[1]);
}
// update all nodes that contain p in first layer
void upd(int u, int l, int r, int p, int q, int64_t k){
//cout << "inserting to : " << l << " " << r << " " << p << " " << q << "\n";
buf[u].rt = ins(buf[u].rt,p,q,k);
//print(buf[u].rt); cout << "\n";
if(l == r) return;
int mid = (l+r)/2;
if(p <= mid){
if(!buf[u].l) buf[u].l = alloc_out();
upd(buf[u].l,l,mid,p,q,k);
} else{
if(!buf[u].r) buf[u].r = alloc_out();
upd(buf[u].r,mid+1,r,p,q,k);
}
}
int64_t query(int u, int l, int r, int l_out, int r_out, int l_in, int r_in){
if(l == l_out && r == r_out){
return query_in(buf[u].rt,l_in,r_in);
}
int mid = (l+r)/2;
if(r_out <= mid){
if(!buf[u].l) return 0;
return query(buf[u].l,l,mid,l_out,r_out,l_in,r_in);
} else if(l_out > mid){
if(!buf[u].r) return 0;
return query(buf[u].r,mid+1,r,l_out,r_out,l_in,r_in);
} else{
int64_t vl = buf[u].l == 0 ? 0 : query(buf[u].l,l,mid,l_out,mid,l_in,r_in);
int64_t vr = buf[u].r == 0 ? 0 : query(buf[u].r,mid+1,r,mid+1,r_out,l_in,r_in);
return gcd(vl,vr);
}
}
void init(int R, int C){
n = R, m = C; pos = ibuf_pos = 0;
alloc_out(); // make root
}
void update(int P, int Q, long long K){
upd(1,0,n-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V){
return query(1,0,n-1,P,U,Q,V);
}
