#include "game.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
struct Node1D{
ll v = 0;
int tag = -1;
Node1D *l = nullptr, *r = nullptr;
};
struct Node2D{
Node1D *rt = nullptr;
Node2D *l = nullptr, *r = nullptr;
};
int n, m;
Node2D *rt = nullptr;
void pull1D(Node1D *node){
node->v = __gcd(node->l == nullptr ? 0 : node->l->v, node->r == nullptr ? 0 : node->r->v);
}
Node1D *modify1D(int pos, ll v, int L, int R, Node1D *node){
if(node == nullptr){
node = new Node1D();
node->v = v;
node->tag = pos;
return node;
}
if(pos == node->tag){
node->v = v;
return node;
}
assert(L != R);
int M = (L + R) / 2;
if(node->tag != -1){
assert(node->l == nullptr && node->r == nullptr);
if(node->tag <= M) node->l = modify1D(node->tag, node->v, L, M, node->l);
else node->r = modify1D(node->tag, node->v, M + 1, R, node->r);
node->tag = -1;
node->v = 0;
}
if(pos <= M) node->l = modify1D(pos, v, L, M, node->l);
else node->r = modify1D(pos, v, M + 1, R, node->r);
pull1D(node);
return node;
}
ll query1D(int l, int r, int L, int R, Node1D *node){
if(node == nullptr) return 0;
if((l <= node->tag && node->tag <= r) || (l == L && r == R)) return node->v;
assert(L != R);
int M = (L + R) / 2;
if(r <= M) return query1D(l, r, L, M, node->l);
else if(l > M) return query1D(l, r, M + 1, R, node->r);
else return __gcd(query1D(l, M, L, M, node->l), query1D(M + 1, r, M + 1, R, node->r));
}
void pull2D(Node2D *node, int y){
ll lv = node->l == nullptr ? 0 : query1D(y, y, 0, m - 1, node->l->rt);
ll rv = node->r == nullptr ? 0 : query1D(y, y, 0, m - 1, node->r->rt);
node->rt = modify1D(y, __gcd(lv, rv), 0, m - 1, node->rt);
}
Node2D *modify2D(int x, int y, ll v, int L, int R, Node2D *node){
if(node == nullptr) node = new Node2D();
if(L == R){
node->rt = modify1D(y, v, 0, m - 1, node->rt);
return node;
}
int M = (L + R) / 2;
if(x <= M) node->l = modify2D(x, y, v, L, M, node->l);
else node->r = modify2D(x, y, v, M + 1, R, node->r);
pull2D(node, y);
return node;
}
ll query2D(int xl, int xr, int yl, int yr, int L, int R, Node2D *node){
if(node == nullptr) return 0;
if(xl == L && xr == R){
return query1D(yl, yr, 0, m - 1, node->rt);
}
int M = (L + R) / 2;
if(xr <= M) return query2D(xl, xr, yl, yr, L, M, node->l);
else if(xl > M) return query2D(xl, xr, yl, yr, M + 1, R, node->r);
else return __gcd(query2D(xl, M, yl, yr, L, M, node->l), query2D(M + 1, xr, yl, yr, M + 1, R, node->r));
}
void init(int R, int C){
n = R; m = C;
}
void update(int P, int Q, long long K){
rt = modify2D(P, Q, K, 0, n - 1, rt);
}
ll calculate(int P, int Q, int U, int V){
return query2D(P, U, Q, V, 0, n - 1, rt);
}
