#include <bits/stdc++.h>
#include "game.h"
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))
using namespace std;
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 x;
node(ll v = 0){ update(v); }
node update(ll v, vector<ll> params = {}){ x = v; return *this; }
static node op(const node& a, const node& b){ return node(gcd2(a.x, b.x)); }
};
template<class T>
class segtree{
int n;
vector<T> tree;
T update(int s, int l, int r, int pos, vector<ll> params){
if (pos < l || pos > r) return tree[s];
if (l == r){
ll x = params[0];
params = vector<ll>(params.begin()+1, params.end());
tree[s].update(x, params);
return tree[s];
}
int m = (l + r)>>1;
T a = update(2*s, l, m, pos, params);
T b = update(2*s+1, m+1, r, pos, params);
return tree[s] = T::op(a, b);
}
T query(int s, int l, int r, int ql, int qr) const {
if (l > qr || r < ql) return T();
if (l >= ql && r <= qr) return tree[s];
int m = (l + r)>>1;
T a = query(2*s, l, m, ql, qr);
T b = query(2*s+1, m+1, r, ql, qr);
return T::op(a, b);
}
public:
segtree<T>(int n = 0, const T& a = T()){ Assign(n, a); }
void Assign(int s, const T& a){
n = highpow(s);
if (bitcnt(s) > 1) n <<= 1;
tree.assign(2*n, a);
}
static segtree<T> op(const segtree<T>& a, const segtree<T>& b){
segtree<T> r(a.n);
for (int i = 1; i < 2*a.n; i++)
r.tree[i] = T::op(a.tree[i], b.tree[i]);
return r;
}
T update(int pos, vector<ll> params){ return update(1, 0, n-1, pos, params); }
T query(int l, int r) const { return query(1, 0, n-1, l, r); }
};
const ll LINF = 4e18;
const int mxN = 1e6+10, INF = 2e9;
ll n, m, a[mxN];
segtree<segtree<node> > st;
void init(int R, int C) {
st.Assign(C, segtree<node>(R));
}
void update(int P, int Q, long long K) {
st.update(Q, {P, K});
}
long long calculate(int P, int Q, int U, int V) {
auto tree = st.query(Q, V);
return tree.query(P, U).x;
}
