#include <bits/stdc++.h>
#include "game.h"
#define ll long long
#define pii pair<int, int>
using namespace std;
const int MAX = (1 << 30) - 1;
const int BRANCH_LOG = 5;
const int BRANCH = (1 << BRANCH_LOG);
const int TREE_SIZE = 22000 * (30 / BRANCH_LOG);
struct SegTree1D{
int nxt = 0;
vector<ll> tree;
vector<int> L, R;
SegTree1D(){
tree.emplace_back(0);
L.emplace_back(0);
R.emplace_back(0);
}
int addNode(){
tree.emplace_back(0);
L.emplace_back(0);
R.emplace_back(0);
return ++nxt;
}
void update(int node, int l, int r, int pos, ll val){
if(l == r){
tree[node] = val;
return;
}
int mid = (l + r) / 2;
if(pos <= mid){
if(!L[node]) L[node] = addNode();
update(L[node], l, mid, pos, val);
}
else{
if(!R[node]) R[node] = addNode();
update(R[node], mid + 1, r, pos, val);
}
tree[node] = 0;
if(L[node]) tree[node] = gcd(tree[node], tree[L[node]]);
if(R[node]) tree[node] = gcd(tree[node], tree[R[node]]);
}
ll ask(int node, int l, int r, int ql, int qr){
if(qr < l || r < ql){
return 0;
}
if(ql <= l && r <= qr){
return tree[node];
}
int mid = (l + r) / 2;
ll ans = 0;
if(L[node]) ans = gcd(ans, ask(L[node], l, mid, ql, qr));
if(R[node]) ans = gcd(ans, ask(R[node], mid + 1, r, ql, qr));
return ans;
}
};
struct SegTree2D{
int nxt = 0;
SegTree1D tree[TREE_SIZE];
int child[TREE_SIZE][BRANCH];
SegTree2D(){
memset(child, 0, sizeof(child));
}
void update(int node, int l, int r, int posY, int posX, ll val){
if(l == r){
tree[node].update(0, 0, MAX, posX, val);
return;
}
ll ans = 0;
int inc = (r - l + 1) >> BRANCH_LOG;
int uChild = (posY - l) / inc;
if(!child[node][uChild]) child[node][uChild] = ++nxt;
update(child[node][uChild], l + uChild * inc, l + (uChild + 1) * inc- 1, posY, posX, val);
for (int i = 0; i < BRANCH; i++)
{
if(child[node][i]) ans = gcd(ans, tree[child[node][i]].ask(0, 0, MAX, posX, posX));
}
tree[node].update(0, 0, MAX, posX, ans);
}
ll ask(int node, int l, int r, int qlY, int qrY, int qlX, int qrX){
if(qrY < l || r < qlY){
return 0;
}
if(qlY <= l && r <= qrY){
return tree[node].ask(0, 0, MAX, qlX, qrX);
}
ll ans = 0;
int inc = (r - l + 1) >> BRANCH_LOG;
int a = l;
for (int i = 0; i < BRANCH; i++)
{
if(child[node][i] && a + inc - 1 >= qlY && a <= qrY){
ans = gcd(ans, ask(child[node][i], a, a + inc - 1, qlY, qrY, qlX, qrX));
}
a += inc;
}
return ans;
}
};
SegTree2D tree;
void init(int R, int C){
}
void update(int P, int Q, ll K){
tree.update(0, 0, MAX, P, Q, K);
}
ll calculate(int P, int Q, int U, int V){
return tree.ask(0, 0, MAX, P, U, Q, V);
}
