#include "game.h"
#include <cstdio>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
inline long long func(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
ii lca(int l,int r,int pos){ //find lca of 2 nodes
if (pos<l){
int p=32-__builtin_clz(pos^l);
int lp=(pos>>p)<<p;
return ii(lp,lp+(1<<p)-1);
}
if (r<pos){
int p=32-__builtin_clz(r^pos);
int lp=(l>>p)<<p;
return ii(lp,lp+(1<<p)-1);
}
}
struct node{
int s,e,m;
long long val=0;
node *l=nullptr,*r=nullptr;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
}
bool inside(int i){
return s<=i && i<=e;
}
void update(int i,long long j){
if (s==e) val=j;
else{
if (i<=m){
if (l==nullptr) l=new node(i,i);
else if (!l->inside(i)){
node *temp=l;
ii child=lca(l->s,l->e,i);
l=new node(child.first,child.second);
if (temp->e<=l->m) l->l=temp;
else l->r=temp;
}
l->update(i,j);
}
else{
if (r==nullptr) r=new node(i,i);
else if (!r->inside(i)){
node *temp=r;
ii child=lca(r->s,r->e,i);
r=new node(child.first,child.second);
if (temp->e<=r->m) r->l=temp;
else r->r=temp;
}
r->update(i,j);
}
val=func((l==nullptr)?0:l->val,(r==nullptr)?0:r->val);
}
}
long long query(int i,int j){
if (i<=s && e<=j) return val;
else if (j<=m) return (l==nullptr)?0:l->query(i,j);
else if (m<i) return (r==nullptr)?0:r->query(i,j);
else return func((l==nullptr)?0:l->query(i,m),(r==nullptr)?0:r->query(m+1,j));
}
node* clone(){
node* res=new node(s,e);
res->val=val;
res->l=(l==nullptr)?nullptr:l->clone();
res->r=(r==nullptr)?nullptr:r->clone();
return res;
}
};
struct node2d{
int s,e,m;
node *val=new node(0,(1<<30)-1);
node2d *l=nullptr,*r=nullptr;
node2d (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
}
bool inside(int i){
return s<=i && i<=e;
}
void update(int i,int j,long long k){
if (s==e) val->update(j,k);
else{
if (i<=m){
if (l==nullptr) l=new node2d(i,i);
else if (!l->inside(i)){
node2d *temp=l;
ii child=lca(l->s,l->e,i);
l=new node2d(child.first,child.second);
if (temp->e<=l->m) l->l=temp;
else l->r=temp;
l->val=temp->val->clone();
}
l->update(i,j,k);
}
else{
if (r==nullptr) r=new node2d(i,i);
else if (!r->inside(i)){
node2d *temp=r;
ii child=lca(r->s,r->e,i);
r=new node2d(child.first,child.second);
if (temp->e<=r->m) r->l=temp;
else r->r=temp;
r->val=temp->val->clone();
}
r->update(i,j,k);
}
val->update(j,func((l==nullptr)?0:l->val->query(j,j),(r==nullptr)?0:r->val->query(j,j)));
}
}
long long query(int i,int j,int i2,int j2){
if (i<=s && e<=j) return val->query(i2,j2);
else if (j<=m) return (l==nullptr)?0:l->query(i,j,i2,j2);
else if (m<i) return (r==nullptr)?0:r->query(i,j,i2,j2);
else return func((l==nullptr)?0:l->query(i,m,i2,j2),(r==nullptr)?0:r->query(m+1,j,i2,j2));
}
}*root=new node2d(0,(1<<30)-1);
void init(int R, int C) {
}
void update(int P, int Q, long long K) {
root->update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return root->query(P,U,Q,V);
}
