#include "game.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
#define y1 ___y1
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + 333;
const int N = 22000;
const int K = 92;
class tree{ public:
int x, y, x1, y1, x2, y2;
ll val, ans;
tree *l, *r;
tree() {
x = y = x1 = y1 = x2 = y2 = -1;
val = ans = 0;
l = r = 0;
}
};
typedef tree* pTree;
int r, c, n, sz, type, x1, y1, x2, y2;
ll k;
map < ii, int > h;
map < ii, ll > M;
pair < ii, ll > a[N];
inline ll gcd(ll a, ll b) {
while(b) {
a %= b;
swap(a, b);
}
return a;
}
bool cmp(pair < ii, ll > x, pair < ii, ll > y) {
if(x.first.second == y.first.second)
return x.first.first < y.first.first;
return x.first.second < y.first.second;
}
void init(pTree t, int l, int r, bool d = 0) {
int m = l + r >> 1;
if(!d)
nth_element(a + l, a + m, a + r + 1);
else
nth_element(a + l, a + m, a + r + 1, cmp);
t -> x = t -> x1 = t -> x2 = a[m].first.first;
t -> y = t -> y1 = t -> y2 = a[m].first.second;
t -> val = t -> ans = a[m].second;
if(l < m) {
if(!t -> l)
t -> l = new tree;
init(t -> l, l, m - 1, !d);
t -> ans = gcd(t -> ans, t -> l -> ans);
t -> x1 = min(t -> x1, t -> l -> x1);
t -> y1 = min(t -> y1, t -> l -> y1);
t -> x2 = max(t -> x2, t -> l -> x2);
t -> y2 = max(t -> y2, t -> l -> y2);
}
if(m < r) {
if(!t -> r)
t -> r = new tree;
init(t -> r, m + 1, r, !d);
t -> ans = gcd(t -> ans, t -> r -> ans);
t -> x1 = min(t -> x1, t -> r -> x1);
t -> y1 = min(t -> y1, t -> r -> y1);
t -> x2 = max(t -> x2, t -> r -> x2);
t -> y2 = max(t -> y2, t -> r -> y2);
}
}
ll query(pTree t) {
if(x2 < t -> x1 or t -> x2 < x1 or y2 < t -> y1 or t -> y2 < y1)
return 0;
if(x1 <= t -> x1 and t -> x2 <= x2 and y1 <= t -> y1 and t -> y2 <= y2)
return t -> ans;
ll ans = 0;
if(x1 <= t -> x and t -> x <= x2 and y1 <= t -> y and t -> y <= y2)
ans = t -> val;
if(t -> l)
ans = gcd(ans, query(t -> l));
if(t -> r)
ans = gcd(ans, query(t -> r));
return ans;
}
void change(pTree t, bool d = 0) {
if(x1 == t -> x and y1 == t -> y) {
t -> val = t -> ans = k;
if(t -> l)
t -> ans = gcd(t -> ans, t -> l -> ans);
if(t -> r)
t -> ans = gcd(t -> ans, t -> r -> ans);
return;
}
if((!d and ii(x1, y1) < ii(t -> x, t -> y)) or (d and ii(y1, x1) < ii(t -> y, t -> x)))
change(t -> l, !d);
else
change(t -> r, !d);
t -> ans = t -> val;
if(t -> l)
t -> ans = gcd(t -> ans, t -> l -> ans);
if(t -> r)
t -> ans = gcd(t -> ans, t -> r -> ans);
}
pTree t;
void init(int R, int C) {
r = R;
c = C;
t = new tree;
}
void update(int x1, int y1, ll k) {
:: x1 = x1;
:: y1 = y1;
:: k = k;
if(h.find(ii(x1, y1)) != h.end()) {
change(t);
a[h[ii(x1, y1)]].second = k;
return;
}
M[ii(x1, y1)] = k;
if(M.size() == K) {
foreach(it, M)
a[sz++] = *it;
M.clear();
init(t, 0, sz - 1);
for(int i = 0; i < sz; i++)
h[a[i].first] = i;
}
}
ll calculate(int x1, int y1, int x2, int y2) {
:: x1 = x1;
:: y1 = y1;
:: x2 = x2;
:: y2 = y2;
ll ans = query(t);
foreach(it, M) {
int x = it -> first.first;
int y = it -> first.second;
ll k = it -> second;
if(x1 <= x and x <= x2 and y1 <= y and y <= y2)
ans = gcd(ans, k);
}
return ans;
}
