#include "game.h"
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <chrono>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <bitset>
#include <cmath>
#include <cassert>
typedef long long ll;
typedef long double ld;
using namespace std;
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;
}
const int maxn = 1 << 30;
struct node
{
int idx;
ll val, g;
node* l, * r;
node() { idx = -1, val = 0, g = 0, l = NULL, r = NULL; }
} st[2 * 60 * 22005];
int cnt = 0;
struct node2d
{
node *n;
node2d* l, * r;
node2d() { n = NULL, l = NULL, r = NULL; }
} st2d[2 * 60 * 22005];
int cnt2 = 0;
void update1d(int idx, ll val, int myl, int myr, node *n)
{
if (myr < idx || myl > idx) return;
if (n->idx == -1 || n->idx == idx) return n->val = val, n->idx = idx, void();
if (n->l == NULL) n->l = &st[cnt++], n->r = &st[cnt++];
update1d(idx, val, myl, (myl + myr) / 2, n->l);
update1d(idx, val, (myl + myr) / 2 + 1, myr, n->r);
n->g = gcd2(gcd2(n->l->val, n->l->g), gcd2(n->r->val, n->r->g));
}
ll query1d(int li, int ri, int myl, int myr, node* n)
{
if (n == NULL || ri < myl || li > myr) return 0;
ll ans = ((li <= n->idx && n->idx <= ri) ? n->val : 0ll);
if (li <= myl && myr <= ri) return gcd2(ans, n->g);
return gcd2(ans, gcd2(query1d(li, ri, myl, (myl + myr) / 2, n->l), query1d(li, ri, (myl + myr) / 2 + 1, myr, n->r)));
}
void update2d(int x, int y, ll val, int myl, int myr, node2d* n)
{
if (myr < x || myl > x) return;
update1d(y, val, 0, maxn - 1, n->n);
if (myl == myr) return;
if (n->l == NULL) n->l = new node2d(), n->l->n = &st[cnt++];
if (n->r == NULL) n->r = new node2d(), n->r->n = &st[cnt++];
update2d(x, y, val, myl, (myl + myr) / 2, n->l);
update2d(x, y, val, (myl + myr) / 2 + 1, myr, n->r);
}
ll query2d(int x1, int y1, int x2, int y2, int myl, int myr, node2d* n)
{
if (n == NULL || x2 < myl || x1 > myr) return 0;
if (x1 <= myl && myr <= x2) return query1d(y1, y2, 0, maxn - 1, n->n);
return gcd2(query2d(x1, y1, x2, y2, myl, (myl + myr) / 2, n->l), query2d(x1, y1, x2, y2, (myl + myr) / 2 + 1, myr, n->r));
}
void init(int R, int C)
{
st2d[cnt2++].n = &st[cnt++];
}
void update(int x, int y, long long k)
{
update2d(x, y, k, 0, maxn - 1, &st2d[0]);
}
long long calculate(int x1, int y1, int x2, int y2)
{
return query2d(x1, y1, x2, y2, 0, maxn - 1, &st2d[0]);
}
