#include <bits/stdc++.h>
#include "game.h"
#define ll long long
#define pii pair<int, int>
using namespace std;
const int TREE_SIZE = 22000 * 31;
const int MAX = 1e9 - 1;
struct SegTree1D{
int nxt = 0;
vector<ll> tree;
vector<int> L, R;
SegTree1D(){
tree.reserve(128);
L.reserve(128);
R.reserve(128);
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, int 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 L[TREE_SIZE], R[TREE_SIZE];
SegTree2D(){
memset(L, 0, sizeof(L));
memset(R, 0, sizeof(R));
}
void update(int node, int l, int r, int posY, int posX, int val){
if(l == r){
tree[node].update(0, 0, MAX, posX, val);
return;
}
int mid = (l + r) / 2;
if(posY <= mid){
if(!L[node]) L[node] = ++nxt;
update(L[node], l, mid, posY, posX, val);
}
else{
if(!R[node]) R[node] = ++nxt;
update(R[node], mid + 1, r, posY, posX, val);
}
ll ans = 0;
if(L[node]) ans = gcd(ans, tree[L[node]].ask(0, 0, MAX, posX, posX));
if(R[node]) ans = gcd(ans, tree[R[node]].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);
}
int mid = (l + r) / 2;
ll ans = 0;
if(L[node]) ans = gcd(ans, ask(L[node], l, mid, qlY, qrY, qlX, qrX));
if(R[node]) ans = gcd(ans, ask(R[node], mid + 1, r, qlY, qrY, qlX, qrX));
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);
}
