#include <bits/stdc++.h>
#include "game.h"
#define pb push_back
//#define DEBUGGING
void __print(int i) { std::cerr << i; }
void __print(long long int i) { std::cerr << i; }
void __print(const char *c) { std::cerr << c; }
template<typename T>
void __print(T& t) { std::cerr <<"{";int f = 0; for (auto& i : t) { std::cerr << ((f++) ? ", ": ""); __print(i); } std::cerr << "}"; }
void _print() { std::cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...); }
#ifdef DEBUGGING
#define debug(x...) std::cerr << "[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...)
#endif
long long gcd(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct SegTree1D
{
std::vector<int> up, down;
std::vector<long long> data;
SegTree1D() : up(1, -1), down(1, -1), data(1, 0) {}
void push(int u, int d, int index)
{
if (d - u == 1)
return;
if (up[index] == -1)
{
up[index] = data.size();
up.pb(-1);
down.pb(-1);
data.pb(0);
}
if (down[index] == -1)
{
down[index] = data.size();
up.pb(-1);
down.pb(-1);
data.pb(0);
}
}
void set(int u, int d, int index, int y, long long val)
{
debug(u, d, index, y, val);
if (y >= d || u > y)
return;
push(u, d, index);
if (u + 1 == d)
{
data[index] = val;
return;
}
int m = u+d>>1;
set(u, m, up[index], y, val);
set(m, d, down[index], y, val);
data[index] = gcd(data[up[index]], data[down[index]]);
}
long long int get(int u, int d, int index, int uu, int dd)
{
if (uu >= d || u >= dd || index == -1)
return 0;
if (dd >= d && u >= uu)
return data[index];
int m = u+d>>1;
long long ures = get(u, m, up[index], uu, dd);
long long dres = get(m, d, down[index], uu, dd);
return gcd(ures, dres);
}
};
std::vector<SegTree1D> st;
std::map<int, int> sts;
int R, C;
struct SegTree2D
{
std::vector<int> up, down, root;
std::vector<int> left, right;
std::vector<long long> data;
SegTree2D() : up(1, -1), down(1, -1), root(1, -1) {}
void push_x(int l, int r, int index)
{
if (r - l == 1)
return;
if (left[index] == -1)
{
left[index] = data.size();
left.pb(-1);
right.pb(-1);
data.pb(0);
}
if (right[index] == -1)
{
right[index] = data.size();
left.pb(-1);
right.pb(-1);
data.pb(0);
}
}
void push_y(int u, int d, int index)
{
if (up[index] == -1 && d - u > 1)
{
up[index] = root.size();
up.pb(-1);
down.pb(-1);
root.pb(-1);
}
if (down[index] == -1 && d - u > 1)
{
down[index] = root.size();
up.pb(-1);
down.pb(-1);
root.pb(-1);
}
if (root[index] == -1)
{
root[index] = data.size();
left.pb(-1);
right.pb(-1);
data.pb(0);
}
}
long long int query1d(int l, int r, int index, int ll, int rr)
{
if (index == -1 || ll >= r || l >= rr)
return 0;
if (rr >= r && l >= ll)
return data[index];
int m = l+r>>1;
long long int lres = query1d(l, m, left[index], ll, rr);
long long int rres = query1d(m, r, right[index], ll, rr);
return gcd(lres, rres);
}
long long int query2d(int u, int d, int index, int uu, int dd, int ll, int rr)
{
if (index == -1 || uu >= d || u >= dd)
return 0;
if (dd >= d && u >= uu)
return query1d(0, C, root[index], ll, rr);
int m = u+d>>1;
long long int ures = query2d(u, m, up[index], uu, dd, ll, rr);
long long int dres = query2d(m, d, down[index], uu, dd, ll, rr);
return gcd(ures, dres);
}
void update1d(int l, int r, int index, int x, long long int val)
{
if (x >= r || l > x)
return;
push_x(l, r, index);
if (l + 1 == r)
{
data[index] = val;
return;
}
int m = l+r>>1;
update1d(l, m, left[index], x, val);
update1d(m, r, right[index], x, val);
data[index] = gcd(data[left[index]], data[right[index]]);
}
void update2d(int u, int d, int index, int y, int x)
{
if (y >= d || u > y)
return;
push_y(u, d, index);
update1d(0, C, root[index], x, st[sts[x]].get(0, R, 0, u, d));
debug(u, d, y, x, root[index], x, st[sts[x]].get(0, R, 0, u, d));
if (u + 1 == d)
return;
int m = u+d>>1;
update2d(u, m, up[index], y, x);
update2d(m, d, down[index], y, x);
}
};
SegTree2D st2;
void init(int r, int c)
{
R = r;
C = c;
}
void update(int P, int Q, long long int K)
{
if (sts.find(Q) == sts.end())
{
sts[Q] = st.size();
st.pb(SegTree1D());
}
st[sts[Q]].set(0, R, 0, P, K);
st2.update2d(0, R, 0, P, Q);
}
long long int calculate(int P, int Q, int U, int V)
{
return st2.query2d(0, R, 0, P, U+1, Q, V+1);
}
