#include<bits/stdc++.h>
#include "game.h"
#define task ""
#define PI acos(-1)
#define fi first
#define sc second
#define ll long long
#define ld long double
#define rep(i, a, b, c) for (int i = a; i <= b; i += c)
#define ford(i, a, b, c) for (int i = a; i >= b; i -= c)
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int inf = 2e9, bsize = 350, maxn = 1e6 + 2, N = 2e5, mod = 998224353;
const long long llinf = 1e18;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef pair<II, II> IV;
int R, C;
struct Node {
Node *left, *right, *par;
int pos = 0;
ll val = 0;
ll GCD = 0;
};
typedef Node* tnode;
tnode nilt;
void upnode(tnode x) {
x->GCD = __gcd(x->left->GCD, __gcd(x->right->GCD, x->val));
}
void link(tnode x, tnode y, bool left) {
y->par = x;
if (left)
x->left = y;
else
x->right = y;
}
void uptree(tnode x) {
tnode y = x->par;
tnode z = y->par;
if (y->left == x) {
link(y, x->right, 1);
link(x, y, 0);
}
else {
link(y, x->left, 0);
link(x, y, 1);
}
if (z != nilt) {
if (z->left == y)
link(z, x, 1);
else
link(z, x, 0);
}
else
x->par = z;
upnode(y);
upnode(x);
}
void splay(tnode x) {
if (x == nilt)
return;
while (x->par != nilt) {
tnode y = x->par;
tnode z = y->par;
if (z != nilt) {
if ((z->left == y) == (y->left == x))
uptree(y);
else
uptree(x);
}
uptree(x);
}
}
tnode Find(tnode &t, int pos) {
if (t == nilt)
return t;
tnode res = nilt;
tnode x = t;
while (x != nilt) {
t = x;
if (pos < x->pos)
x = x->left;
else {
res = x;
x = x->right;
}
}
splay(t);
return res;
}
void split(tnode T, int pos, tnode &T1, tnode &T2) {
T1 = Find(T, pos);
if (T1 == nilt)
T2 = T;
else {
splay(T1);
T2 = T1->right;
T1->right = T2->par = nilt;
upnode(T1);
}
}
tnode join(tnode T1, tnode T2) {
if (T1 == nilt)
return T2;
while (T1->right != nilt)
T1 = T1->right;
splay(T1);
if (T2 != nilt)
link(T1, T2, 0);
upnode(T1);
return T1;
}
void ins(tnode &root, int pos, ll val) {
if (root == nilt) {
root = new Node();
root->left = root->right = root->par = nilt;
root->pos = pos;
root->val = root->GCD = val;
return;
}
tnode p = Find(root, pos);
if (p == nilt) {
tnode x = root;
root = new Node();
root->left = root->right = root->par = nilt;
root->pos = pos;
root->val = val;
link(root, x, 0);
upnode(root);
return;
}
root = p;
splay(root);
if (p->pos < pos) {
tnode x, y;
x = root;
y = x->right;
y->par = x->right = nilt;
upnode(x);
root = new Node();
root->left = root->right = root->par = nilt;
root->pos = pos;
root->val = val;
if (x != nilt)
link(root, x, 1);
if (y != nilt)
link(root, y, 0);
upnode(root);
return;
}
root->val = val;
upnode(root);
}
ll take(tnode &root, int pos) {
tnode p = Find(root, pos);
if (p == nilt || p->pos != pos)
return 0;
return p->val;
}
struct IT {
tnode x;
int left = -1;
int right = -1;
};
vector<IT> it;
void up(int r, int Q) {
ll Left = (it[r].left == -1) ? 0 : take(it[it[r].left].x, Q);
ll Right = (it[r].right == -1) ? 0 : take(it[it[r].right].x, Q);
ins(it[r].x, Q, __gcd(Left, Right));
}
void update2D(int r, int lo, int hi, int P, int Q, ll k) {
if (lo == hi) {
ins(it[r].x, Q, k);
return;
}
int mid = (lo + hi)/2;
if (P <= mid) {
if (it[r].left == -1) {
it.emplace_back();
it[r].left = it.size() - 1;
it[it[r].left].x = nilt;
}
update2D(it[r].left, lo, mid, P, Q, k);
}
else {
if (it[r].right == -1) {
it.emplace_back();
it[r].right = it.size() - 1;
it[it[r].right].x = nilt;
}
update2D(it[r].right, mid + 1, hi, P, Q, k);
}
up(r, Q);
}
ll get(int r, int lo, int hi, int P, int Q, int U, int V) {
if (hi < P || Q < lo || r == -1)
return 0;
if (P <= lo && hi <= Q) {
if (it[r].x == nilt)
return 0;
tnode x, y, z;
split(it[r].x, U - 1, x, y);
split(y, V, y, z);
ll ans = y->GCD;
it[r].x = join(x, join(y, z));
return ans;
}
int mid = (lo + hi)/2;
return __gcd(get(it[r].left, lo, mid, P, Q, U, V), get(it[r].right, mid + 1, hi, P, Q, U, V));
}
void init(int _R, int _C) {
nilt = new Node();
it.emplace_back();
it[0].x = nilt;
R = _R;
C = _C;
}
void update(int P, int Q, ll K) {
update2D(0, 0, R - 1, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return get(0, 0, R - 1, P, U, Q, V);
}
