#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<30), M=21142005, 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());
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(){
g=val;
if(l)g=gcd2(l->g, g);
if(r)g=gcd2(r->g, g);
}
};
node* merge(node* u, node* v){
if(!u)return v;
if(!v)return u;
assert(u->key < v->key);
if((v->rank)>(u->rank)){
v->l=merge(u, v->l);
v->upd();
return v;
}
else{
u->r=merge(u->r, v);
u->upd();
return u;
}
}
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
typedef pair<node*, node*> pnn;
pnn split(node* v, int l){
if(!v)return mp(nullptr, nullptr);
if(v->key<l){
pnn a=split(v->r, l);
v->r=a.st;
v->upd();
a.st=v;
return a;
}
else{
pnn a=split(v->l, l);
v->l=a.nd;
v->upd();
a.nd=v;
return a;
}
}
void wyp(node* v){
if(!v) return;
wyp(v->l);
cout<<v->rank<<" "<<v->key<<" "<<v->val<<" "<<v->g<<"\n";
wyp(v->r);
}
/*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(node* 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=b.st->g;
assert(b.st->key >=l && b.st -> key <=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;
}*/
node* upd1d(node* v, int i, ll val){
pnn a=split(v, i);
pnn b=split(a.nd, i+1);
if(b.st){
assert(b.st->key == i);
b.st->val=val;
}
else b.st=new node(i, val);
b.st->upd();
a.nd=merge(b.st, b.nd);
return merge(a.st, a.nd);
}
int wsk2=1;
int l2[K], r2[K];
node* 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) {
/* ... */
for(int i=0; i<K; i++)nodes[i]=nullptr;
}
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);
}
