#include "game.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define MOD 1000000007
#define N 10000005
#define M 1000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;
struct treap {
int key,pri;
int l,r;
ll val,g;
} T[N];
int root;
int go[N],l[N],r[N];
int tot_T,tot_S;
long long gcd2(long long X, long long Y) {
if(X<Y) swap(X,Y);
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void make2(int& node,int pos,ll val) {
if(!node) {
node=++tot_T;
T[node].key=pos;
T[node].pri=rand();
T[node].l=T[node].r=0;
}
T[node].g=T[node].val=val;
}
void make1(int& node) {
if(!node) node=++tot_S;
}
void relax(int root) {
T[root].g=gcd2(gcd2(T[T[root].l].g,T[T[root].r].g),T[root].val);
}
void merge(int& root,int l,int r) {
if(!l || !r) root=(l?l:r);
else if(T[l].pri>T[r].pri) {
merge(T[l].r,T[l].r,r);
root=l;
}
else {
merge(T[r].l,l,T[r].l);
root=r;
}
if(root) relax(root);
}
void split(int root,int to,int& l,int& r) {
if(!root) l=r=0;
else if(T[root].key<=to) {
split(T[root].r,to,T[root].r,r);
l=root;
}
else {
split(T[root].l,to,l,T[root].l);
r=root;
}
if(root) relax(root);
}
ll get2(int& root,int l,int r) {
int r1,r2,r3;
split(root,r,r1,r3);
split(r1,l-1,r1,r2);
ll res=T[r2].g;
merge(root,r1,r2);
merge(root,root,r3);
return res;
}
ll get1(int& node,int bas,int son,int a,int b,int c,int d) {
if(!node) return 0;
if(bas>=a && son<=c) return get2(go[node],b,d);
if(orta>=a && orta+1<=c) return gcd2(get1(l[node],bas,orta,a,b,c,d),get1(r[node],orta+1,son,a,b,c,d));
if(orta>=a) return get1(l[node],bas,orta,a,b,c,d);
return get1(r[node],orta+1,son,a,b,c,d);
}
void up2(int& root,int pos,ll val) {
int r1,r2,r3;
split(root,pos,r1,r3);
split(r1,pos-1,r1,r2);
make2(r2,pos,val);
merge(root,r1,r2);
merge(root,root,r3);
}
void up1(int& node,int bas,int son,int x,int y,ll val) {
make1(node);
if(bas==x && son==x) {
up2(go[node],y,val);
return ;
}
if(orta>=x) up1(l[node],bas,orta,x,y,val);
else up1(r[node],orta+1,son,x,y,val);
ll g=gcd2(get2(go[l[node]],y,y),get2(go[r[node]],y,y));
up2(go[node],y,g);
}
void init(int R, int C) {
T[0].g=T[0].val=T[0].l=T[0].r=0;
srand(time(NULL));
}
void update(int P, int Q, long long K) {
up1(root,0,inf-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return get1(root,0,inf-1,P,Q,U,V);
}
