#include "game.h"
#include <iostream>
#include <numeric>
using namespace std;
// const int N=1e9;
int R,C;
class AVL{
public:
class node{
public:
long long subtree_gcd=0,own_value=0;
int height,key,mx=-1e9,mi=1e9;
node * left;
node * right;
node(int k,long long tp){
height = 1;
mx=mi=k;
key = k;
subtree_gcd=tp;
own_value=tp;
left = NULL;
right = NULL;
}
};
node * root = NULL;
int n;
void Update(int& x,long long& val){
root=insertUtil(root, x,val);
}
long long get(int& l,int& r)
{
// cout<<"GCd for "<<l<<' '<<r<<" is "<<get(root,l,r)<<endl;
return get(root,l,r);
}
void print()
{
print(root);
}
private:
void Rectify(node * head)
{
if(head==NULL)
return;
head->subtree_gcd=head->own_value;
head->mx=head->key;
head->mi=head->key;
if(head->left!=NULL)
{
head->mx=max(head->mx,head->left->mx);
head->mi=min(head->mi,head->left->mi);
head->subtree_gcd=gcd(head->subtree_gcd,head->left->subtree_gcd);
}
if(head->right!=NULL)
{
head->mx=max(head->mx,head->right->mx);
head->mi=min(head->mi,head->right->mi);
head->subtree_gcd=gcd(head->subtree_gcd,head->right->subtree_gcd);
}
}
void print(node* h)
{
if(h==NULL)
return;
print(h->left);
cout<<h->key<<' '<<h->mi<<' '<<h->mx<<' '<<h->own_value<<' '<<h->subtree_gcd<<endl;
print(h->right);
}
int height(node * head){
if(head==NULL) return 0;
return head->height;
}
node * rightRotation(node * head){
node * newhead = head->left;
head->left = newhead->right;
newhead->right = head;
head->height = 1+max(height(head->left), height(head->right));
newhead->height = 1+max(height(newhead->left), height(newhead->right));
Rectify(head);
Rectify(newhead);
return newhead;
}
node * leftRotation(node * head){
node * newhead = head->right;
head->right = newhead->left;
newhead->left = head;
head->height = 1+max(height(head->left), height(head->right));
newhead->height = 1+max(height(newhead->left), height(newhead->right));
Rectify(head);
Rectify(newhead);
return newhead;
}
long long get(node* head,int& l,int& r)
{
if(head==NULL)
return 0;
if(head->mx<l or r<head->mi)
return 0;
if(l<=head->mi and head->mx<=r)
return head->subtree_gcd;
long long ans=gcd(get(head->left,l,r),get(head->right,l,r));
if(l<=head->key and head->key<=r)
{
ans=gcd(ans,head->own_value);
}
return ans;
}
node * insertUtil(node * head, int& x,long long& tp){
if(head==NULL){
n+=1;
node * temp = new node(x,tp);
return temp;
}
if(head->key==x)
{
head->own_value=tp;
Rectify(head);
return head;
}
if(x < head->key) head->left = insertUtil(head->left, x,tp);
else if(x > head->key) head->right = insertUtil(head->right, x,tp);
Rectify(head);
head->height = 1 + max(height(head->left), height(head->right));
int bal = height(head->left) - height(head->right);
if(bal>1){
if(x < head->left->key){
return rightRotation(head);
}else{
head->left = leftRotation(head->left);
return rightRotation(head);
}
}else if(bal<-1){
if(x > head->right->key){
return leftRotation(head);
}else{
head->right = rightRotation(head->right);
return leftRotation(head);
}
}
return head;
}
};
struct SegmentTree2D
{
AVL heavy;
SegmentTree2D* next[2];
SegmentTree2D(int l,int r)
{
next[0]=next[1]=NULL;
}
long long get(int& sx,int& ex,int& sy,int& ey,int s=0,int e=R-1)
{
if(ex<s or e<sx)
return 0;
if(sx<=s and e<=ex)
return heavy.get(sy,ey);
long long ans=0;
if(next[0]!=NULL)
ans=gcd(ans,next[0]->get(sx,ex,sy,ey,s,(s+e)/2));
if(next[1]!=NULL)
ans=gcd(ans,next[1]->get(sx,ex,sy,ey,1+((s+e)/2),e));
return ans;
}
void Update(int& l,int& r,long long& val,int s=0,int e=R-1)
{
if(s==e)
{
heavy.Update(r,val);
return;
}
long long gdc=0;
if(l<=((s+e)/2))
{
if(next[0]==NULL)
next[0]=new SegmentTree2D(s,(s+e)/2);
next[0]->Update(l,r,val,s,(s+e)/2);
}
else
{
if(next[1]==NULL)
next[1]=new SegmentTree2D(1+((s+e)/2),e);
next[1]->Update(l,r,val,1+((s+e)/2),e);
}
if(next[0]!=NULL)
gdc=gcd(gdc,next[0]->heavy.get(r,r));
if(next[1]!=NULL)
gdc=gcd(gdc,next[1]->heavy.get(r,r));
heavy.Update(r,gdc);
}
};
SegmentTree2D* st;
void init(int r, int c)
{
C=c;
R=r;
st=new SegmentTree2D(0,R-1);
}
void update(int p, int q, long long k)
{
st->Update(p,q,k);
}
long long calculate(int P, int Q, int U, int V)
{
return st->get(P,U,Q,V);
}
