#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;}
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define vint(x) vector<int> x
#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<<((long long)(bi)))
#define coutarr(x) for (auto &it : x) cout<<it<<endl;
typedef long long ll;
const ll INF = LONG_LONG_MAX;
const int MOD = 1e9+7;
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 MINX = 0;
const int MAXX = 1e9+7;
const int MINY = 0;
const int MAXY = 1e9+7;
struct SegTree2D{
struct SegTree{
struct Node{
int lnode, rnode;
ll val;
Node():lnode(-1),rnode(-1),val(0ll){}
};
vector<Node> segtree;
inline int dall(int node){
if (segtree[node].lnode==-1){
segtree[node].lnode=segtree.size();
segtree.push_back(Node());
}
return segtree[node].lnode;
}
inline int dalr(int node){
if (segtree[node].rnode==-1){
segtree[node].rnode=segtree.size();
segtree.push_back(Node());
}
return segtree[node].rnode;
}
SegTree(){
lnode=rnode=-1;
segtree.push_back(Node());
}
int lnode, rnode;
void update(int x, int val, int l = MINY, int r = MAXY, int node = 0){
if (l==r && l==x){
segtree[node].val=val;
return;
}
if (l>x || r<x) return;
int mid = l+(r-l)/2;
if (x<=mid){
update(x, val, l, mid, dall(node));
}
else {
update(x, val, mid+1, r, dalr(node));
}
ll lnode = 0, rnode = 0;
if (segtree[node].lnode!=-1) lnode = segtree[segtree[node].lnode].val;
if (segtree[node].rnode!=-1) rnode = segtree[segtree[node].rnode].val;
segtree[node].val=gcd2(lnode, rnode);
}
ll query(int tarl, int tarr, int l = MINY, int r = MAXY, int node = 0){
if (node==-1) return 0;
if (l>=tarl && r<=tarr) return segtree[node].val;
if (l>tarr || r<tarl) return 0;
int mid = l+(r-l)/2;
ll lnode = query(tarl, tarr, l, mid, segtree[node].lnode);
ll rnode = query(tarl, tarr, mid+1, r, segtree[node].rnode);
return gcd2(lnode, rnode);
}
};
vector<SegTree> segtree;
SegTree2D(){segtree.push_back(SegTree());}
inline int dall(int node){
if (segtree[node].lnode==-1){
segtree[node].lnode=segtree.size();
segtree.push_back(SegTree());
}
return segtree[node].lnode;
}
inline int dalr(int node){
if (segtree[node].rnode==-1){
segtree[node].rnode=segtree.size();
segtree.push_back(SegTree());
}
return segtree[node].rnode;
}
ll query(int tarl, int tarr, int x1, int x2, int l = MINX, int r = MAXX, int node = 0){
if (node==-1) return 0;
if (l>=tarl && r<=tarr) return segtree[node].query(x1,x2);
if (l>tarr || r<tarl) return 0;
int mid = l+(r-l)/2;
ll lnode = query(tarl, tarr, x1, x2, l, mid, segtree[node].lnode);
ll rnode = query(tarl, tarr, x1, x2, mid+1, r, segtree[node].rnode);
return gcd2(lnode, rnode);
}
void update(int x, int y, ll val, int l = MINX, int r = MAXX, int node = 0){
if (l==x && r==x){
segtree[node].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, dall(node));
else update(x, y, val, mid+1, r, dalr(node));
int left = segtree[node].lnode, right = segtree[node].rnode;
int pt = 0, ptl = 0, ptr = 0;
if (left==-1) ptl = -1;
if (right==-1) ptr = -1;
l=MINY, r=MAXY;
while (true){
ll sag = 0, sol = 0;
if (ptl!=-1) sol=segtree[left].segtree[ptl].val;
if (ptr!=-1) sag=segtree[right].segtree[ptr].val;
segtree[node].segtree[pt].val=gcd2(sol,sag);
if (l==r) break;
int mid = l+(r-l)/2;
if (y<=mid){
if (ptl!=-1) ptl=segtree[left].segtree[ptl].lnode;
if (ptr!=-1) ptr=segtree[right].segtree[ptr].lnode;
pt=segtree[node].dall(pt);
r=mid;
}
else {
if (ptl!=-1) ptl=segtree[left].segtree[ptl].rnode;
if (ptr!=-1) ptr=segtree[right].segtree[ptr].rnode;
pt=segtree[node].dalr(pt);
l=mid+1;
}
}
}
};
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);
}
