#include <bits/stdc++.h>
#include "game.h"
#pragma GCC optimize("O2")
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define fi first
#define se second
using namespace std;
const int lim = 1e9 + 5;
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;
}
struct nodex {
int l = -1, r = -1, nx = -1;
};
struct nodey {
int l = -1, r = -1;
ll val = 0;
};
const int lim2 = 2.2e7;
struct segtree {
vector<nodex> vx;
vector<nodey> vy;
segtree() {
vx.pb(nodex());
vx.pb(nodex());
vx.reserve(lim2);
vy.reserve(lim2);
}
int add_nodex() {
vx.pb(nodex());
return (int)vx.size() - 1;
}
int add_nodey() {
vy.pb(nodey());
return (int)vy.size() - 1;
}
void update_node(int nd) {
vy[nd].val = 0;
if(vy[nd].l != -1)
vy[nd].val = gcd2(vy[vy[nd].l].val, vy[nd].val);
if(vy[nd].r != -1)
vy[nd].val = gcd2(vy[vy[nd].r].val, vy[nd].val);
}
void update_x(int x, int y, ll val) {
int nd = 1, cl = 0, cr = lim - 1;
vector<int> nodes = {nd};
while(cl < cr) {
int mid = (cl + cr) >> 1;
if(x <= mid) {
cr = mid;
if(vx[nd].l == -1)
vx[nd].l = add_nodex();
nd = vx[nd].l;
}
else {
cl = mid + 1;
if(vx[nd].r == -1)
vx[nd].r = add_nodex();
nd = vx[nd].r;
}
nodes.pb(nd);
}
reverse(nodes.begin(), nodes.end());
// from smallest to largest
for(auto x : nodes) {
if(vx[x].nx == -1)
vx[x].nx = add_nodey();
update_y(vx[x].nx, x, y, val);
}
}
void update_y(int nd, int ndx, int y, ll val) {
int cl = 0, cr = lim - 1;
vector<int> nodes = {nd};
while(cl < cr) {
int mid = (cl + cr) >> 1;
if(y <= mid) {
cr = mid;
if(vy[nd].l == -1)
vy[nd].l = add_nodey();
nd = vy[nd].l;
}
else {
cl = mid + 1;
if(vy[nd].r == -1)
vy[nd].r = add_nodey();
nd = vy[nd].r;
}
nodes.pb(nd);
}
nodes.pop_back();
reverse(nodes.begin(), nodes.end());
if(vx[ndx].l == -1 && vx[ndx].r == -1)
vy[nd].val = val;
else {
// take from v[ndx].l and v[ndx].r
vy[nd].val = gcd2(vx[ndx].l != -1 ? query_y(vx[vx[ndx].l].nx, 0, lim - 1, y, y) : 0, vx[ndx].r != -1 ? query_y(vx[vx[ndx].r].nx, 0, lim - 1, y, y) : 0);
}
for(auto x : nodes) {
// cerr << "UPDATE " << x << endl;
update_node(x);
}
}
ll query_x(int nd, int cl, int cr, int l, int r, int y1, int y2) {
if(nd == -1 || cl > r || cr < l)
return 0;
else if(cl >= l && cr <= r) {
// cerr << "GET Y " << cl << " " << cr << endl;
// cerr << l << " " << r << " " << y1 << " " << y2 << endl;
return query_y(vx[nd].nx, 0, lim - 1, y1, y2);
}
else {
int mid = (cl + cr) >> 1;
return gcd2(query_x(vx[nd].l, cl, mid, l, r, y1, y2), query_x(vx[nd].r, mid + 1, cr, l, r, y1, y2));
}
}
ll query_y(int nd, int cl, int cr, int l, int r) {
if(nd == -1 || cl > r || cr < l)
return 0;
else if(cl >= l && cr <= r) {
// cerr << "GOT Y " << nd << " " << cl << " " << cr << " " << v[nd].val << endl;
return vy[nd].val;
}
else {
int mid = (cl + cr) >> 1;
return gcd2(query_y(vy[nd].l, cl, mid, l, r), query_y(vy[nd].r, mid + 1, cr, l, r));
}
}
};
segtree seg;
void init(int R, int C) {
}
void update(int P, int Q, long long K) {
seg.update_x(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
// cerr << "QUERY " << endl;
return seg.query_x(1, 0, lim - 1, P, U, Q, V);
}
