#pragma GCC optimize("Ofast")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
long long gcd2(long long X, long long Y) {
long long tmp;
if(X==0&&Y==0) return 0;
if(X==0) return Y;
if(Y==0) return X;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int R, C;
struct colSegmentTree {
unordered_map<ll, ll> st;
void update(ll val, int j, colSegmentTree *leftChild=NULL, colSegmentTree *rightChild=NULL, ll id=1, int l=0, int r=C) {
if(l>j || r<=j) return;
if(r-l==1) {
if(leftChild==NULL&&rightChild==NULL) st[id] = val;
else if(leftChild==NULL) st[id] = rightChild->st[id];
else if(rightChild==NULL) st[id] = leftChild->st[id];
else st[id] = gcd2(leftChild->st[id], rightChild->st[id]);
return;
}
int mid = (l+r)/2;
if(j < mid) update(val, j, leftChild, rightChild, id*2 , l, mid);
else update(val, j, leftChild, rightChild, id*2+1, mid, r);
if(st.count(id*2 )&&
st.count(id*2+1))
st[id] = gcd2(st[id*2], st[id*2+1]);
else if(st.count(id*2 ))
st[id] = st[id*2 ];
else if(st.count(id*2+1))
st[id] = st[id*2+1];
}
ll query(int x, int y, ll id=1, int l=0, int r=C) {
if(l>=y || r<=x) return 0;
if(!st.count(id)) return 0;
if(l>=x && r<=y) {
// cerr << " " << l << " " << r-1 << endl;
return st[id];
}
int mid = (l+r)/2;
return gcd2(query(x, y, id*2 , l, mid),
query(x, y, id*2+1, mid, r));
}
};
struct rowSegmentTree {
unordered_map<ll, colSegmentTree> st;
void update(ll val, int i, int j, ll id=1, int l=0, int r=R) {
if(l+1==r) {
// leftChild = NULL; rightChild = NULL;
st[id].update(val, j);
return;
}
int mid = (l+r)/2;
if(i < mid) update(val, i, j, id*2 , l, mid);
else update(val, i, j, id*2+1, mid, r);
// leftChild = &st[id*2 ];
// rightChild = &st[id*2+1];
if(!st.count(id*2)&&!st.count(id*2+1)) st[id].update(val, j, NULL, NULL);
else if(!st.count(id*2)) st[id].update(val, j, NULL, &st[id*2+1]);
else if(!st.count(id*2+1)) st[id].update(val, j, &st[id*2], NULL);
else st[id].update(val, j, &st[id*2], &st[id*2+1]);
}
ll query(int x, int y, int nx, int ny, ll id=1, int l=0, int r=R) {
if(l>=y || r<=x) return 0;
if(!st.count(id)) return 0;
if(l>=x && r<=y) {
// cerr << l << " " << r-1 << endl;
return st[id].query(nx, ny);
}
int mid = (l+r)/2;
return gcd2(query(x, y, nx, ny, id*2 , l, mid),
query(x, y, nx, ny, id*2+1, mid, r));
}
};
rowSegmentTree tree;
void init(signed r, signed c) {
R = 1000000000;
C = 1000000000;
// for(int i = 0; i < R; i++)
// for(int j = 0; j < C; j++)
// update(i,j,rand());
/* ... */
}
void update(signed P, signed Q, long long K) {
tree.update(K, P, Q);
/* ... */
}
long long calculate(signed P, signed Q, signed U, signed V) {
/* ... */
return tree.query(P, U+1, Q, V+1);
}
void test() {
// for(int P = 0; P < 1000000000; P++)
// for(int Q = 0; Q < 1000000000; Q++)
// for(int U = P; U < 1000000000; U++)
// for(int V = Q; V < 1000000000; V++)
// cerr << tree.query(P, U+1, Q, V+1) << endl;
}
