// In the name of Allah
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int sq = 150;
const int maxn = sq * sq;
const int maxlg = 15;
vector<int> arr1, arr2;
vector<pair<pll, ll>> A;
vector<pll> Ax[maxn], Asq[sq];
int indx[maxn], indsq[maxn];
ll Rx[maxn][maxlg], Rsq[maxn][maxlg];
int GI1(int x) {
return lower_bound(all(arr1), x) - arr1.begin();
}
int GI2(int x) {
return lower_bound(all(arr2), x) - arr2.begin();
}
int Gx(int i, int r) {
return indx[r] + i;
}
int Gsq(int i, int r) {
return indsq[r] + i;
}
void addx(int R) {
for (int x : arr1) {
if (R == x) return ;
}
arr1.pb(R); int j = len(arr1) - 1;
while (j - 1 >= 0 && arr1[j] < arr1[j - 1]) {
swap(arr1[j], arr1[j - 1]); j--;
}
}
void add_val(pair<pll, ll> R) {
int j = 0;
for (auto f : A) {
if (R.F == f.F) {
A[j].S = R.S;
return ;
}
j++;
}
A.pb(R); j = len(A) - 1;
while (j - 1 >= 0 && A[j] < A[j - 1]) {
swap(A[j], A[j - 1]); j--;
}
}
void init(int R, int C) {
return ;
}
void calx(int ind) {
int n = len(Ax[ind]);
for (int i = n - 1; i >= 0; i--) {
Rx[Gx(i, ind)][0] = Ax[ind][i].S;
for (int j = 1; j < maxlg; j++) {
int k = i + (1 << (j - 1));
if (k >= n) break;
Rx[Gx(i, ind)][j] = __gcd(Rx[Gx(i, ind)][j - 1], Rx[Gx(k, ind)][j - 1]);
}
}
}
void calsq(int ind) {
int n = len(Asq[ind]);
for (int i = n - 1; i >= 0; i--) {
Rsq[Gsq(i, ind)][0] = Asq[ind][i].S;
for (int j = 1; j < maxlg; j++) {
int k = i + (1 << (j - 1));
if (k >= n) break;
Rsq[Gsq(i, ind)][j] = __gcd(Rsq[Gsq(i, ind)][j - 1], Rsq[Gsq(k, ind)][j - 1]);
}
}
}
void update(int i, int j, ll x) {
addx(i); swap(arr1, arr2); addx(j); swap(arr1, arr2);
add_val(Mp(Mp(i, j), x));
for (int i = 0; i < len(arr2); i++) Ax[i].clear();
for (int i = 0; i < len(arr2); i += sq) Asq[i / sq].clear();
for (auto f : A) {
int i = GI1(f.F.F), j = GI2(f.F.S); ll x = f.S;
Ax[j].pb(Mp(i, x));
Asq[j / sq].pb(Mp(i, x));
}
for (int i = 0; i < len(arr2); i++) {
if (i == 0) indx[i] = 0;
else indx[i] = len(Ax[i - 1]) + indx[i - 1];
calx(i);
}
for (int i = 0; i < len(arr2); i += sq) {
if (i == 0) indsq[i] = 0;
else indsq[i] = len(Asq[i - 1]) + indsq[i - 1];
calsq(i / sq);
}
}
ll get_val(int ind, int l, int r) {
l = lower_bound(all(Ax[ind]), (pll) Mp(l, -1)) - Ax[ind].begin();
r = lower_bound(all(Ax[ind]), (pll) Mp(r, -1)) - Ax[ind].begin();
if (r - l <= 0) return 0;
int j = __lg(r - l);
return __gcd(Rx[Gx(l, ind)][j], Rx[Gx(r - (1 << j), ind)][j]);
}
ll get_valx(int ind, int l, int r) {
l = lower_bound(all(Asq[ind]), (pll) Mp(l, -1)) - Asq[ind].begin();
r = lower_bound(all(Asq[ind]), (pll) Mp(r, -1)) - Asq[ind].begin();
if (r - l <= 0) return 0;
int j = __lg(r - l);
return __gcd(Rsq[Gsq(l, ind)][j], Rsq[Gsq(r - (1 << j), ind)][j]);
}
ll calculate(int l1, int l2, int r1, int r2) {
r1++; r2++;
l1 = GI1(l1); r1 = GI1(r1);
l2 = GI2(l2); r2 = GI2(r2);
ll res = 0;
if (r2 - l2 <= 2 * sq) {
for (int i = l2; i < r2; i++) {
res = __gcd(res, get_val(i, l1, r1));
}
}
else {
int lx = (l2 / sq) + (l2 % sq != 0), rx = r2 / sq;
for (int i = l2; i < lx; i++) {
res = __gcd(res, get_val(i, l1, r1));
}
for (int i = lx; i < rx; i += sq) {
res = __gcd(res, get_valx(i / sq, l1, r1));
}
for (int i = rx; i < r2; i++) {
res = __gcd(res, get_val(i, l1, r1));
}
}
return res;
}
