#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<30), M=5e6, K=682005;
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;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int wsk1=1;
int l1[M], r1[M], Rank[M], Key[M];
ll val1[M], g[M];
/*struct node{
node* l=nullptr, *r=nullptr;
int Rank, Key;
ll val, g;
node(int _Key, ll _val): Key(_Key), val(_val), g(_val) {Rank=rng();}
};*/
void upd(int v){
g[v]=val1[v];
if(l1[v])g[v]=gcd2(g[l1[v]], g[v]);
if(r1[v])g[v]=gcd2(g[r1[v]], g[v]);
}
int merge(int u, int v){
if(!u)return v;
if(!v)return u;
assert(Key[u] < Key[v]);
if(Rank[v]>Rank[u]){
l1[v]=merge(u, l1[v]);
upd(v);
return v;
}
else{
r1[u]=merge(r1[u], v);
upd(u);
return u;
}
}
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
typedef pair<int, int> pnn;
pnn split(int v, int l){
if(!v)return mp(0, 0);
if(Key[v]<l){
pnn a=split(r1[v], l);
r1[v]=a.st;
upd(v);
a.st=v;
return a;
}
else{
pnn a=split(l1[v], l);
l1[v]=a.nd;
upd(v);
a.nd=v;
return a;
}
}
void wyp(int v){
if(!v) return;
wyp(l1[v]);
cout<<Rank[v]<<" "<<Key[v]<<" "<<val1[v]<<" "<<g[v]<<"\n";
wyp(r1[v]);
}
/*int wsk1=1;
int l1[M], r1[M];
ll val1[M];
void upd(int v){
if(!v)return;
val1[v]=gcd2(val1[l1[v]], val1[r1[v]]);
}
ll quer1d(int v, int L, int R, int l, int r){
if(!v)return 0;
//cout<<L<<" "<<R<<" "<<v->val<<"q\n";
if(l==L && r==R){
return val1[v];
}
int M=(L+R)>>1;
ll ans=0;
if(l<=M)ans=gcd2(ans, quer1d(l1[v], L, M, l, min(M, r)));
if(r>M)ans=gcd2(ans, quer1d(r1[v], M+1, R, max(l, M+1), r));
return ans;
}*/
ll quer1d(int v, int l, int r){
//wyp(v);
//cout<<l<<" "<<r<<"\n";
pnn a=split(v, l);
pnn b=split(a.nd, r+1);
ll ans=0;
if(b.st){
ans=g[b.st];
assert(Key[b.st] >=l && Key[b.st] <=r);
}
a.nd=merge(b.st, b.nd);
assert(merge(a.st, a.nd)==v);
//cout<<ans<<"\n";
return ans;
}
/*int upd1d(int v, int L, int R, int i, ll val){
if(!v)v=wsk1++;
if(L==R){
//cout<<v->val<<" "<<val<<" "<<i<<"u\n";
val1[v]=val;
return v;
}
//cout<<L<<" "<<R<<" "<<v->val<<"a\n";
int M=(L+R)>>1;
if(i<=M)l1[v]=upd1d(l1[v], L, M, i, val);
else r1[v]=upd1d(r1[v], M+1, R, i, val);
upd(v);
//cout<<L<<" "<<R<<" "<<v->val<<"b\n";
return v;
}*/
int upd1d(int v, int i, ll val){
pnn a=split(v, i);
pnn b=split(a.nd, i+1);
if(b.st){
assert(Key[b.st] == i);
val1[b.st]=val;
}
else{
b.st=wsk1;
val1[wsk1]=val;
g[wsk1]=val;
Key[wsk1]=i;
Rank[wsk1]=rng();
wsk1++;
}
upd(b.st);
a.nd=merge(b.st, b.nd);
return merge(a.st, a.nd);
}
int wsk2=1;
int l2[K], r2[K];
int nodes[K];
ll quer2d(int v, int L, int R, int l, int r, int x, int y){
if(!v)return 0;
if(l==L && r==R){
return quer1d(nodes[v], x, y);
}
int M=(L+R)>>1;
ll ans=0;
if(l<=M)ans=gcd2(ans, quer2d(l2[v], L, M, l, min(M, r), x, y));
if(r>M)ans=gcd2(ans, quer2d(r2[v], M+1, R, max(l, M+1), r, x, y));
return ans;
}
int upd2d(int v, int L, int R, int i, int j, ll val){
if(!v)v=wsk2++;
if(L==R){
//cout<<L<<" "<<R<<" "<<i<<" "<<j<<"\n";
nodes[v]=upd1d(nodes[v], j, val);
return v;
}
int M=(L+R)>>1;
if(i<=M)l2[v]=upd2d(l2[v], L, M, i, j, val);
else r2[v]=upd2d(r2[v], M+1, R, i, j, val);
//cout<<L<<" "<<R<<" "<<i<<" "<<j<<"\n";
nodes[v]=upd1d(nodes[v], j, gcd2(quer1d(nodes[l2[v]], j, j), quer1d(nodes[r2[v]], j, j)));
return v;
}
int root=0;
void init(int R, int C) {
/* ... */
}
void update(int P, int Q, long long K) {
root=upd2d(root, 0, N-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return quer2d(root, 0, N-1, P, U, Q, V);
}
