//#pragma GCC optimize("O3")
//#pragma GCC target("tune=native")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "game.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define shit short int
#define ll long long
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
//using namespace __gnu_pbds;
//template <typename T1, typename T2>
//using indexed_set = tree<pair<T1, T2>, null_type, less<pair<T1, T2>>, rb_tree_tag, tree_order_statistics_node_update>;
ll nsd(ll a, ll b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
class treap {
struct node {
node* l = nullptr;
node* r = nullptr;
ll val, nsd;
int key, priority;
node(ll val1, int key1) {
val = val1, key = key1;
priority = rand();
nsd = val1;
}
};
typedef node* pnode;
pnode root = nullptr;
ll get_nsd(pnode t) {
if (!t) return 0;
return t->nsd;
}
void update(pnode t) {
if (!t) return;
t->nsd = nsd(nsd(get_nsd(t->l), get_nsd(t->r)), t->val);
return;
}
bool porovnaj(int a1, int a2, int b1, int b2) {
if (a1 == b1) {
return a2 > b2;
}
return a1 > b1;
}
void split(pnode t, int key, pnode& l, pnode& r) {
if (!t) {
l = r = nullptr;
return;
}
if (t->key >= key) {
split(t->l, key, l, t->l);
r = t;
}
else {
split(t->r, key, t->r, r);
l = t;
}
update(t);
return;
}
void merge(pnode& t, pnode l, pnode r) {
if (!l || !r) {
t = l ? l : r;
return;
}
if (l->priority > r->priority) {
merge(l->r, l->r, r);
t = l;
}
else {
merge(r->l, l, r->l);
t = r;
}
update(t);
return;
}
void insert(pnode& t, pnode x) {
if (!t) {
t = x;
return;
}
if (x->priority > t->priority) {
split(t, x->key, x->l, x->r);
t = x;
}
else {
insert(t->key >= x->key ? t->l : t->r, x);
}
update(t);
return;
}
bool najdi(pnode& t, int key, int val) {
if (!t) return 0;
bool odp = 0;
if (t->key == key) {
t->val = val;
odp = 1;
}
else {
odp = najdi(t->key >= key ? t->l : t->r, key, val);
}
update(t);
return odp;
}
public:
void zmen(int key, ll val) {
bool mame = najdi(root, key, val);
if(!mame) insert(root, new node(val, key));
return;
}
ll daj(int a, int b) {
pnode l, r;
l = r = nullptr;
split(root, a, root, r);
split(r, b + 1, l, r);
ll odp = get_nsd(l);
merge(root, root, l);
merge(root, root, r);
return odp;
}
};
class intervalac {
int n;
struct node {
node* l = nullptr;
node* r = nullptr;
treap in;
};
typedef node* pnode;
pnode root = new node;
void propagate(pnode t) {
if (!t->l) t->l = new node;
if (!t->r) t->r = new node;
return;
}
void zmen(pnode t, int l, int r, int a, int b, ll k) {
if (a > r || a < l) return;
if (r == l) {
t->in.zmen(b, k);
return;
}
propagate(t);
int m = (l + r) / 2;
zmen(t->l, l, m, a, b, k); zmen(t->r, m + 1, r, a, b, k);
t->in.zmen(b, nsd(t->l->in.daj(b, b), t->r->in.daj(b, b)));
return;
}
ll daj(pnode t, int l, int r, int a, int b, int c, int d) {
if (a > r || b < l) return 0;
if (a <= l && r <= b) {
return t->in.daj(c, d);
}
propagate(t);
int m = (l + r) / 2;
return nsd(daj(t->l, l, m, a, b, c, d), daj(t->r, m + 1, r, a, b, c, d));
}
public:
void postav(int vel) {
n = vel;
return;
}
void zmen(int p, int q, ll k) {
zmen(root, 0, n - 1, p, q, k);
return;
}
ll daj(int p, int q, int u, int v) {
return daj(root, 0, n - 1, p, q, u, v);
}
};
intervalac seg;
void init(int r2, int c2) {
int r = r2, c = c2;
seg.postav(r);
return;
}
void update(int p, int q, ll k) {
seg.zmen(p, q, k);
return;
}
ll calculate(int p, int q, int u, int v) {
return seg.daj(p, u, q, v);
}
/*
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int r, c, q; cin >> r >> c >> q;
init(r, c);
For(i, q) {
int t; cin >> t;
if (t == 1) {
int p, q; ll k; cin >> p >> q >> k;
update(p, q, k);
}
if (t == 2) {
int p, q, u, v;
cin >> p >> q >> u >> v;
cout << calculate(p, q, u, v) << '\n';
}
}
return 0;
}*/
