#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll gcd2(ll X,ll Y){
while(Y!=0)tie(X,Y)=make_pair(Y,X%Y);
return X;
}
int n,m;
struct Node{
ll val;
int l,r;
Node():val(0LL),l(0),r(0){}
}node[14000000];
int cur_node=0;
struct SegTree{
int root;
SegTree():root(0){}
ll get(int t){
return t?node[t].val:0LL;
}
void modify(int l,int r,int &t,int x,ll v){
if(!t)t=++cur_node;
if(l==r)return void(node[t].val=v);
int m=(l+r)/2;
if(x<=m)modify(l,m,node[t].l,x,v);
else modify(m+1,r,node[t].r,x,v);
node[t].val=gcd2(get(node[t].l),get(node[t].r));
}
void modify(int x,ll v){
modify(0,m-1,root,x,v);
}
ll query(int l,int r,int &t,int x,int y){
if(y<l||r<x||!t)return 0LL;
if(x<=l&&r<=y)return node[t].val;
int m=(l+r)/2;
return gcd2(query(l,m,node[t].l,x,y),query(m+1,r,node[t].r,x,y));
}
ll query(int x,int y){
return query(0,m-1,root,x,y);
}
};
struct SegTree2D{
struct Node{
SegTree tree;
int l,r;
Node():tree(),l(),r(){}
}node[600000];
int root,cur_node;
SegTree2D():root(0),cur_node(0){}
ll get(int t,int x){
return t?node[t].tree.query(x,x):0LL;
}
void modify(int l,int r,int &t,int x,int y,ll v){
if(!t)t=++cur_node;
if(l<r){
int m=(l+r)/2;
if(x<=m)modify(l,m,node[t].l,x,y,v);
else modify(m+1,r,node[t].r,x,y,v);
v=gcd2(get(node[t].l,y),get(node[t].r,y));
}
node[t].tree.modify(y,v);
}
void modify(int x,int y,ll v){
modify(0,n-1,root,x,y,v);
}
ll query(int l,int r,int &t,int x,int y,int x2,int y2){
if(y<l||r<x||!t)return 0LL;
if(x<=l&&r<=y)return node[t].tree.query(x2,y2);
int m=(l+r)/2;
return gcd2(query(l,m,node[t].l,x,y,x2,y2),query(m+1,r,node[t].r,x,y,x2,y2));
}
ll query(int x,int y,int x2,int y2){
return query(0,n-1,root,x,y,x2,y2);
}
}seg;
void init(int R,int C){
n=R,m=C;
}
void update(int P,int Q,ll K){
seg.modify(P,Q,K);
}
ll calculate(int P,int Q,int U,int V){
return seg.query(P,U,Q,V);
}
