#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include "game.h"
#define pn node*
#define ps segtree*
using namespace std;
const int N = 1e9;
const int inf = 2e9;
typedef long long ll;
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;
}
struct node {
ll val;
int key;//index
int prior;
ll ans_tree;
int maxkey, minkey;
node *l, *r;
node(int _X = 0, ll valu = 0ll) {
key = _X;
val = valu;
ans_tree = val;
maxkey = minkey = key;
prior = rand();
l = r = NULL;
}
};
inline void upd_ans(pn &t) {
if (t) {
t->ans_tree = gcd2(t->val, gcd2(t->l ? t->l->ans_tree : 0ll, t->r ? t->r->ans_tree : 0ll));
t->minkey = min(t->key, min(t->l ? t->l->minkey:inf,t->r ? t->r->minkey:inf));
t->maxkey = max(t->key, max(t->l ? t->l->maxkey : -inf, t->r ? t->r->maxkey : -inf));
}
}
void split(pn t, pn &l, pn &r, int key) {
if (!t) {
l = r = NULL; return;
}
if (t->key > key) {
split(t->l, l, t->l, key); r = t;
}
else {
split(t->r, t->r, r, key); l = t;
}
upd_ans(l);
upd_ans(r);
}
void merge(pn &t, pn l, pn r) {
if (!l || !r) {
t = l ? l : r;
}
else {
if (l->prior > r->prior) {
merge(l->r, l->r, r); t = l;
}
else {
merge(r->l, l, r->l); t = r;
}
}
upd_ans(t);
}
void insert(pn &t, pn it) {
if (!t) {
t = it;
}
else {
if (t->prior < it->prior) {
split(t, it->l, it->r, it->key); t = it;
}
else{
if (t->key > it->key) {
insert(t->l, it);
}
else insert(t->r, it);
}
}
upd_ans(t);
}
void erase(pn &t, int key) {
if (!t)return;
if (t->key == key) {
merge(t, t->l, t->r);
}
else {
if (t->key > key)erase(t->l, key);
else erase(t->r, key);
}
upd_ans(t);
}
struct segtree {
node *down;
segtree *l, *r;
segtree(node *U = NULL) {
down = U;
l = r = NULL;
}
};
ps root;
ps next_sg() {
static segtree SEG[2000 * 1000];
static int c1 = 0;
return &SEG[c1++];
}
pn next_node() {
static node an[2000 * 1000];
static int c2 = 0;
return &an[c2++];
}
void init(int R, int C) {
/* ... */
srand(2781);
}
void printt(pn t, int lv = 0) {
if (!t)return;
printt(t->l, lv + 1);
cout << " LEVEL " << lv << " " << t->val << " " << t->ans_tree << " " << t->key << " " << t->prior << endl;
printt(t->r, lv + 1);
}
ll get_ans(pn t, int key) {
if (!t)return 0ll;
if (t->key == key)return t->val;
else {
if (t->key > key) {
return get_ans(t->l, key);
}
else return get_ans(t->r, key);
}
}
void update_sg(int x, int y, long long vl, ps& t, int l, int r) {
if (!t) {
t = next_sg();
}
if (l == r) {
erase(t->down, y);
pn cur = new node(y, vl);
insert(t->down, cur);
}
else {
int m = (l + r) / 2;
if (x <= m)update_sg(x, y, vl, t->l, l, m);
else update_sg(x, y, vl, t->r, m + 1, r);
ll a1 = t->l ? get_ans(t->l->down, y) : 0ll;
ll a2 = t->r ? get_ans(t->r->down, y) : 0ll;
erase(t->down, y);
pn cur = new node(y, gcd2(a1, a2));
insert(t->down, cur);
}
}
void update(int P, int Q, long long K) {
update_sg(P, Q, K, root, 0, N);
}
long long query_y(int l, int r, pn t) {
if (!t)return 0ll;
//printt(t);
//cout << l << " <- || -> " << r << endl;
if (t->maxkey<l || t->minkey>r)return 0ll;
if (t->maxkey <= r && t->minkey >= l)return t->ans_tree;
long long cur = gcd2(query_y(l, r, t->r), query_y(l, r, t->l));
if (t->key >= l && t->key <= r)
cur = gcd2(cur, t->val);
return cur;
}
long long query_x(int xx, int xy, int yx, int yy, ps t, int l, int r) {
if (!t)return 0ll;
if (xx <= l&&r <= xy) {
return query_y(yx, yy, t->down);
}
else {
int m = (l + r) / 2;
long long cur = 0;
if (xx <= m)cur = gcd2(cur, query_x(xx, xy, yx, yy, t->l, l, m));
if (xy> m)cur = gcd2(cur, query_x(xx, xy, yx, yy, t->r, m + 1, r));
return cur;
}
}
long long calculate(int P, int Q, int U, int V) {
return query_x(P, U, Q, V, root, 0, N);
}
