#include "game.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define W(x) ((x) ? (x)->w : 0)
#define ID(x, y) (((long long)(x) << 30) + (y))
using namespace std;
inline long long gcd(long long x, long long y) {
while (x && y) {
if (x > y) x = x % y;
else y = y % x;
}
return x | y;
}
struct Node {
long long x; long long y, w; int fix;
int l, r;
Node *lson, *rson;
Node() {fix = rand(), lson = rson = NULL;}
void pushup() {
w = gcd(y, gcd(W(lson), W(rson))), l = r = (x >> 30);
if (lson) l = lson->l;
if (rson) r = rson->r;
}
}NODEPOOL[700000], *NODECUR = NODEPOOL;
typedef pair <Node *, Node *> pnn;
Node *merge(Node *l, Node *r) {
if (!l || !r) return l ? l : r;
if (l->fix > r->fix) {
l->rson = merge(l->rson, r);
l->pushup();
return l;
} else {
r->lson = merge(l, r->lson);
r->pushup();
return r;
}
}
pnn split(Node *T, long long x) {
if (!T) return pnn(NULL, NULL);
if (x < T->x) {
pnn t = split(T->lson, x);
T->lson = t.se, T->pushup();
return mp(t.fi, T);
} else {
pnn t = split(T->rson, x);
T->rson = t.fi, T->pushup();
return mp(T, t.se);
}
}
void Insert(Node *&T, int x, int y, long long w) {
pnn t1 = split(T, ID(y, x - 1)), t2 = split(t1.se, ID(y, x));
if (!t2.fi) t2.fi = NODECUR++;
t2.fi->x = ID(y, x), t2.fi->y = t2.fi->w = w, t2.fi->l = t2.fi->r = y;
T = merge(t1.fi, merge(t2.fi, t2.se));
}
long long Query(Node *T, const int &l, const int &r) {
if (!T || T->l > r || T->r < l) return 0;
if (l <= T->l && T->r <= r) return T->w;
if ((T->x >> 30) < l) return Query(T->rson, l, r);
if ((T->x >> 30) > r) return Query(T->lson, l, r);
return gcd(T->y, gcd(Query(T->lson, l, r), Query(T->rson, l, r)));
}
struct Seg {
Node *T;
Seg *lson, *rson;
Seg() {T = NULL, lson = rson = NULL;}
}SEGPOOL[700000], *SEGCUR = SEGPOOL, *T = NULL;
void Update(Seg *&T, int l, int r, int x, int y, long long w) {
if (!T) T = SEGCUR++;
Insert(T->T, x, y, w);
if (l == r) return ;
int mid = l + r >> 1;
if (x <= mid) Update(T->lson, l, mid, x, y, w);
else Update(T->rson, mid + 1, r, x, y, w);
}
long long Query(Seg *T, int l, int r, int L, int R, int LL, int RR) {
if (!T) return 0;
if (l == L && r == R) return Query(T->T, LL, RR);
int mid = l + r >> 1;
if (R <= mid) return Query(T->lson, l, mid, L, R, LL, RR);
if (L > mid) return Query(T->rson, mid + 1, r, L, R, LL, RR);
return gcd(Query(T->lson, l, mid, L, mid, LL, RR), Query(T->rson, mid + 1, r, mid + 1, R, LL, RR));
}
int N, M, Q;
void read(int &x) {
char c = getchar(); while (c < '0' || c > '9') c = getchar();
x = c - '0', c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
void read(long long &x) {
char c = getchar(); while (c < '0' || c > '9') c = getchar();
x = c - '0', c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
char st[100];
void print(long long x) {
int tp = 0;
if (!x) st[tp++] = '0';
while (x) st[tp++] = x % 10 + '0', x /= 10;
while (tp--) putchar(st[tp]);
putchar('\n');
}
void init(int R, int C) {
N = R, M = C, srand(2333);
}
void update(int x1, int y1, long long w) {
x1++, y1++;
Update(T, 1, N, x1, y1, w);
}
long long calculate(int x1, int x2, int y1, int y2) {
x1++, x2++, y1++, y2++;
return Query(T, 1, N, x1, y1, x2, y2);
}
