#include "game.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd( time(NULL) );
#define LL long long
#define ls tree[node].l
#define rs tree[node].r
const int maxN = 2.2e4 + 10;
struct Treap
{
int l, r;
int ly, ry, key, v;
LL val, g;
}tree[maxN * 35 + 1];
struct Seg
{
int l, r;
int rt;
}T[maxN * 35 + 1];
int rt, cnt, ct, R, C;
LL gcd2(LL X, LL Y)
{
LL tmp;
while(X != Y && Y != 0)
{
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int new_Node(int y, LL v)
{
tree[++ cnt] = (Treap){0, 0, y, y, (int)rnd(), y, v, v};
return cnt;
}
void pushup(int node)
{
tree[node].ly = ls ? tree[ls].ly : tree[node].v;
tree[node].ry = rs ? tree[rs].ry : tree[node].v;
tree[node].g = gcd2(tree[ls].g, gcd2(tree[node].val, tree[rs].g));
}
void split(int node, int k, int &u, int &v)
{
if(!node) { u = v = 0; return; }
if(tree[node].v <= k) u = node, split(rs, k, tree[u].r, v);
else v = node, split(ls, k, u, tree[v].l);
pushup(node);
}
int merge(int u, int v)
{
if(!u || !v) return u | v;
if(tree[u].key < tree[v].key)
{
tree[u].r = merge(tree[u].r, v);
return pushup(u), u;
}
else
{
tree[v].l = merge(u, tree[v].l);
return pushup(v), v;
}
}
void modify(int &rt, int k, LL val)
{
int u, v, w;
split(rt, k, u, v);
split(u, k - 1, u, w);
if(!w) w = new_Node(k, val);
else tree[w].val = tree[w].g = val;
rt = merge(merge(u, w), v);
}
LL ask(int node, int x, int y)
{
if(!node || tree[node].ly > y || tree[node].ry < x) return 0;
if(x <= tree[node].ly && tree[node].ry <= y) return tree[node].g;
LL ans = 0;
if(x <= tree[node].v && tree[node].v <= y) ans = tree[node].val;
ans = gcd2(ans, gcd2(ask(ls, x, y), ask(rs, x, y)));
return ans;
}
void change(int &node, int l, int r, int x, int y, LL v)
{
if(!node) node = ++ ct;
if(l == r) { modify(T[node].rt, y, v); return; }
int mid = (l + r) >> 1;
if(x <= mid) change(T[node].l, l, mid, x, y, v);
else change(T[node].r, mid + 1, r, x, y, v);
modify(T[node].rt, y, gcd2(ask(T[ T[node].l ].rt, y, y), ask(T[ T[node].r ].rt, y, y)));
}
LL query(int node, int l, int r, int x, int y, int xb, int yb)
{
if(!node) return 0;
if(x <= l && r <= y) return ask(T[node].rt, xb, yb);
int mid = (l + r) >> 1; LL ans = 0;
if(x <= mid) ans = gcd2(ans, query(T[node].l, l, mid, x, y, xb, yb));
if(y > mid) ans = gcd2(ans, query(T[node].r, mid + 1, r, x, y, xb, yb));
return ans;
}
void update(int x, int y, LL v)
{
change(rt, 0, R - 1, x, y, v);
}
LL calculate(int xa, int ya, int xb, int yb)
{
return query(rt, 0, R - 1, xa, xb, ya, yb);
}
void init(int r, int c)
{
R = r; C = c;
}
