#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> ostream& operator<<(ostream& os, vector<X> v){for (auto &it : v) os<<it<<" ";return os;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> v){for (auto &it : v) os<<it<<" ";return os;}
ostream& operator<<(ostream& os, bool bl){return os<<(int32_t)bl;}
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for(auto &it : x) cin>>it;
#define coutarr(x) for(auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1ll<<((int)(bi)))
typedef long long ll;
const ll INF = LONG_LONG_MAX;
const ll MOD = 1e9+9;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "game.h"
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
const int LIMN=1e9;
const int LIMM=1e9;
struct SegTree{
struct Node{
int l, r;
Node *lnode, *rnode;
long long val;
Node(int tl=0, int tr=LIMM):l(tl),r(tr),lnode(nullptr),rnode(nullptr),val(0){}
};
Node *root;
SegTree():root(new Node()){}
void update(int x, long long val, Node *node=nullptr){
if (node==nullptr) node = root;
int l = node->l;
int r = node->r;
if (l==r){
node->val=val;
return;
}
int mid = l+(r-l)/2;
Node** child;
bool left = false;
if (x<=mid) child=&node->lnode,left=true;
else child=&node->rnode;
if ((*child)==nullptr){
(*child)=new Node(x,x);
(*child)->val=val;
}
else if ((*child)->l <= x && (*child)->r >= x){
update(x, val, (*child));
}
else {
if (x<=mid)r=mid;
else l=mid+1;
mid=l+(r-l)/2;
while ((x<=mid) == ((*child)->r<=mid)){
if (x<=mid)r=mid;
else l=mid+1;
mid=l+(r-l)/2;
}
Node *cur = new Node(l,r);
if ((*child)->l<x) cur->lnode=(*child);
else cur->rnode=*child;
if (left) node->lnode=cur;
else node->rnode=cur;
update(x, val, cur);
}
long long updval = 0;
if (node->lnode!=nullptr) updval=gcd2(updval, node->lnode->val);
if (node->rnode!=nullptr) updval=gcd2(updval, node->rnode->val);
node->val=updval;
}
long long query(int tarl, int tarr, Node *node=nullptr, bool first=true){
if (first) node=root;
if (node==nullptr) return 0;
int l = node->l;
int r = node->r;
if (l>=tarl && r<=tarr){
return node->val;
}
if (l>tarr || r<tarl) return 0;
assert(!first || node->lnode || node->rnode);
long long lnode = query(tarl, tarr, node->lnode, false);
long long rnode = query(tarl, tarr, node->rnode, false);
return gcd2(lnode, rnode);
}
};
struct SegTree2D{
struct Node{
Node *lnode, *rnode;
SegTree segtree;
Node():lnode(nullptr),rnode(nullptr),segtree(){}
Node *crl(){
if (lnode==nullptr) lnode=new Node();
return lnode;
}
Node* crr(){
if (rnode==nullptr) rnode=new Node();
return rnode;
}
};
Node *root;
SegTree2D():root(new Node()){}
void update(int x, int y, long long val, int l = 0, int r = LIMN, Node* node=nullptr){
if (l==0 && r==LIMN) node = root;
if (l==r){
node->segtree.update(y,val);
return;
}
if (l>x || r<x) return;
int mid = l+(r-l)/2;
if (x<=mid){
update(x, y, val, l, mid, node->crl());
}
else {
update(x, y, val, mid+1, r, node->crr());
}
long long updval = 0;
if (node->lnode!=nullptr) updval=gcd2(updval, node->lnode->segtree.query(y,y));
if (node->rnode!=nullptr) updval=gcd2(updval, node->rnode->segtree.query(y,y));
node->segtree.update(y,updval);
}
long long query(int tarl, int tarr, int _l, int _r, int l = 0, int r = LIMN, Node* node=nullptr){
if (l==0 && r==LIMN) node = root;
if (node==nullptr) return 0;
if (l>=tarl && r<=tarr){
return node->segtree.query(_l, _r);
}
if (l>tarr || r<tarl) return 0;
int mid = l+(r-l)/2;
long long lnode = query(tarl, tarr, _l, _r, l, mid, node->lnode);
long long rnode = query(tarl, tarr, _l, _r, mid+1, r, node->rnode);
return gcd2(lnode, rnode);
}
};
SegTree2D segtree;
void init(int R, int C) {
/* ahmet23 really orz!.. */
}
void update(int P, int Q, long long K) {
segtree.update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return segtree.query(P,U,Q,V);
}
