#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int lg=30;
int kaf=(1<<lg);
int n,m;
long long gcd(long long a,long long b){
if(a==0){
return b;
}
if(b==0){
return a;
}
return gcd(b,a%b);
}
struct node{
int cl,cr;
char lnk;
long long gc;
node(){
cl=cr=-1;
lnk=gc=0;
}
}fake;
vector<node>allnode;
int te;
void init(int R, int C) {
//hehe
te=2;
allnode.resize(2);
allnode[0].lnk=1;
}
int getr(int u){
if(allnode[u].cr==-1){
if(allnode[u].lnk==0){
allnode.push_back(fake);
allnode[u].cr=(int)allnode.size()-1;
}else{
allnode.push_back(fake);
allnode[u].cr=(int)allnode.size()-1;
allnode.back().lnk=1;
allnode.push_back(fake);
}
}
return allnode[u].cr;
}
int getl(int u){
if(allnode[u].cl==-1){
if(allnode[u].lnk==0){
allnode.push_back(fake);
allnode[u].cl=(int)allnode.size()-1;
}else{
allnode.push_back(fake);
allnode[u].cl=(int)allnode.size()-1;
allnode.back().lnk=1;
allnode.push_back(fake);
}
}
return allnode[u].cl;
}
void asl(int u1,int u2,int u3,int l,int r,int tr){
if(l>r||!(tr>=l&&tr<=r)){
return ;
}
//allnode[u1].gc=gcd(allnode[u2].gc,allnode[u3].gc);
if(u2==-1){
allnode[u1].gc=allnode[u3].gc;
}else if(u3==-1){
allnode[u1].gc=allnode[u2].gc;
}else{
allnode[u1].gc=gcd(allnode[u2].gc,allnode[u3].gc);
}
if(l==r){
return;
}
int m=(l+r)>>1;
int l1,l2,l3,r1,r2,r3;
if(u2==-1||allnode[u2].cl==-1){
l2=-1;
}else{
l2=allnode[u2].cl;
}
if(u3==-1||allnode[u3].cl==-1){
l3=-1;
}else{
l3=allnode[u3].cl;
}
if(u2==-1||allnode[u2].cr==-1){
r2=-1;
}else{
r2=allnode[u2].cr;
}
if(u3==-1||allnode[u3].cr==-1){
r3=-1;
}else{
r3=allnode[u3].cr;
}
asl(getl(u1),l2,l3,l,m,tr);
asl(getr(u1),r2,r3,m+1,r,tr);
}
void calc(int u,int tr){
if(allnode[u].lnk==0){
return ;
}
int cl=getl(u);
int cr=getr(u);
asl(u+1,cl+1,cr+1,0,kaf-1,tr);
}
void upd(int u,int l,int r,int tl,int tr,long long w){
if(l>r||l>tl||r<tl){
return ;
}
if(l==r){
if(allnode[u].lnk==0){
allnode[u].gc=w;
}else{
upd(u+1,0,kaf-1,tr,tl,w);
}
return ;
}
int m=(l+r)>>1;
if(tl<=m){
upd(getl(u),l,m,tl,tr,w);
}else{
upd(getr(u),m+1,r,tl,tr,w);
}
if(allnode[u].lnk==1){
calc(u,tr);
}else{
//allnode[u].gc=gcd(allnode[getl(u)].gc,allnode[getr(u)].gc);
if(allnode[u].cl==-1){
allnode[u].gc=allnode[allnode[u].cr].gc;
}else if(allnode[u].cr==-1){
allnode[u].gc=allnode[allnode[u].cl].gc;
}else{
allnode[u].gc=gcd(allnode[getl(u)].gc,allnode[getr(u)].gc);
}
}
}
long long pors(int u,int l,int r,int tl,int tr,int tl2,int tr2){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
if(l>=tl&&r<=tr){
if(allnode[u].lnk==0){
return allnode[u].gc;
}else{
return pors(u+1,0,kaf-1,tl2,tr2,tl,tr);
}
}
int m=(l+r)>>1;
return gcd(pors(getl(u),l,m,tl,tr,tl2,tr2),pors(getr(u),m+1,r,tl,tr,tl2,tr2));
}
void update(int P,int Q, long long K) {
upd(0,0,kaf-1,P,Q,K);
}
long long calculate(int P,int Q,int U,int V) {
return pors(0,0,kaf-1,P,U,Q,V);
}
