#include "game.h"
//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
template<class T>
void ckmin(T &a, T b)
{
a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
a = max(a, b);
}
long long randomize(long long mod)
{
return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
#define y1 ___y1
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;
#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
long long normalize(long long x, long long mod = INF)
{
return (((x % mod) + mod) % mod);
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll comb(ll a, ll b)
{
return (b == 0 ? a : comb(b, a % b));
}
int N, M;
struct node
{
node *ch[2][2];
ll val;
node()
{
val = 0;
ch[0][0] = ch[0][1] = nullptr;
ch[1][0] = ch[1][1] = nullptr;
}
};
ll getval(node *t)
{
return (t ? t -> val : 0);
}
node *root;
map<pair<int, pii>, ll> mpchild;
map<pii, node*> mphead;
int creationz;
node* upd(node *t, int Lx, int Rx, int Ly, int Ry, int x, int y, ll v)
{
if (x < Lx || x > Rx || y < Ly || y > Ry)
{
return t;
}
if (!t)
{
t = new node();
creationz++;
}
if (Ly == 0 && Ry == M - 1 && Lx != Rx)
{
int mid = (Lx + Rx) / 2;
node *lchild = mphead[MP(Lx, mid)], *rchild = mphead[MP(mid + 1, Rx)];
if (!lchild) lchild = new node();
if (!rchild) rchild = new node();
lchild = upd(lchild, Lx, mid, Ly, Ry, x, y, v);
rchild = upd(rchild, mid + 1, Rx, Ly, Ry, x, y, v);
mphead[MP(Lx, mid)] = lchild;
mphead[MP(mid + 1, Rx)] = rchild;
// t -> ch[0][0] = upd(t -> ch[0][0], Lx, mid, Ly, Ry, x, y, v);
// t -> ch[0][1] = upd(t -> ch[0][1], mid + 1, Rx, Ly, Ry, x, y, v);
}
if (Ly == Ry)
{
if (Lx == Rx)
{
t -> val = v;
}
else
{
int mid = (Lx + Rx) / 2;
t -> val = comb(mpchild[MP(Ly, MP(Lx, mid))], mpchild[MP(Ly, MP(mid + 1, Rx))]);
}
mpchild[MP(Ly, MP(Lx, Rx))] = t -> val;
}
else
{
int mid = (Ly + Ry) / 2;
t -> ch[1][0] = upd(t -> ch[1][0], Lx, Rx, Ly, mid, x, y, v);
t -> ch[1][1] = upd(t -> ch[1][1], Lx, Rx, mid + 1, Ry, x, y, v);
t -> val = comb(getval(t -> ch[1][0]), getval(t -> ch[1][1]));
}
return t;
}
ll query(node *t, int Lx, int Rx, int Ly, int Ry, int x1, int x2, int y1, int y2)
{
if (x2 < Lx || x1 > Rx || y2 < Ly || y1 > Ry)
{
return 0;
}
if (!t)
{
return 0;
}
if (x1 <= Lx && Rx <= x2)
{
if (y1 <= Ly && Ry <= y2)
{
return t -> val;
}
int mid = (Ly + Ry) / 2;
return comb(query(t -> ch[1][0], Lx, Rx, Ly, mid, x1, x2, y1, y2), query(t -> ch[1][1], Lx, Rx, mid + 1, Ry, x1, x2, y1, y2));
}
int mid = (Lx + Rx) / 2;
return comb(query(mphead[MP(Lx, mid)], Lx, mid, Ly, Ry, x1, x2, y1, y2), query(mphead[MP(mid + 1, Rx)], mid + 1, Rx, Ly, Ry, x1, x2, y1, y2));
}
void init(int r, int c)
{
N = max(2, r);
M = max(2, c);
root = new node();
}
void update(int x, int y, ll v)
{
upd(root, 0, N - 1, 0, M - 1, x, y, v);
}
ll calculate(int x1, int y1, int x2, int y2)
{
return query(root, 0, N - 1, 0, M - 1, x1, x2, y1, y2);
}
