#include "game.h"
#include"bits/stdc++.h"
#define pb push_back
#define ll long long
#define pii pair<ll,ll>
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
const ll inf = 1000000000;
const ll maxn = 2e5;
ll r , c , n ;
//Treap
struct node
{
node *l , *r;
ll pri , val , gcd , pos;
node(){}
node(ll _val , ll _pos){
l=r=nullptr;
pri = rand() , val = _val , gcd=_val , pos = _pos;
}
inline void up(){
ll a = 0 , b = 0;
if(l!=nullptr) a = l->gcd;
if(r!=nullptr) b = r->gcd;
gcd = __gcd(val,__gcd(a , b));
}
}mem[maxn<<3];
node *merge(node *a , node *b){
if(a == nullptr) return b;
if(b == nullptr) return a;
if(a->pri < b->pri){
a->r = merge(a->r , b);
return a->up() , a;
}
else{
b->l = merge(a , b->l);
return b->up() , b;
}
}
void split(node *root , node *&a , node *&b , ll pos){
if(root == nullptr) return a=b=nullptr , void();
if(root->pos <= pos){
a = root;
split(root->r , a->r , b , pos);
}
else{
b = root;
split(root->l , a , b->l , pos);
}
root->up();
}
ll top = 0;
void insert(node *&root , ll val , ll pos){
node *a=nullptr , *b=nullptr , *c=nullptr , *d=nullptr;
split(root , a , b , pos);
split(a , c , d , pos-1);
if(d == nullptr) mem[top]=node(val,pos) , a = merge(c , &mem[top++]) ;
else d->val = val , d->gcd = val , a = merge(c , d);
root = merge(a , b);
}
ll query(node *&root , ll l , ll r, ll x1 , ll x2){
ll res = 0;
node *a , *b , *c , *d;
split(root , a , b , l-1);
split(b , c , d , r);
if(c != nullptr) res = c->gcd;
root = merge(a , merge(c , d));
return res;
}
//Segment Tree
struct st
{
st *lc , *rc;
node *treap;
st(){
lc = rc = nullptr;
treap = nullptr;
}
}*stroot=nullptr,stmem[maxn<<3];
ll sttop;
ll st_query(ll l , ll r , ll x1 , ll x2 , ll y1 , ll y2 , st *rt){
if(rt == nullptr) return 0;
if(rt->treap == nullptr) return 0;
if(x1 <= l && r <= x2) return query(rt->treap , y1 , y2 , l , r);
ll mid = (l+r)>>1;
if(x2 <= mid) return st_query(l , mid , x1 , x2 , y1 , y2 , rt->lc);
else if(x1 > mid) return st_query(mid+1 , r , x1 , x2 , y1 , y2 , rt->rc);
else return __gcd(st_query(l , mid , x1 , x2 , y1 , y2 , rt->lc)
,st_query(mid+1 , r , x1 , x2 , y1 , y2 , rt->rc));
}
void modify(ll l , ll r , ll x , ll y , ll val , st *&rt){
if(rt == nullptr) stmem[sttop]=st() , rt = &stmem[sttop++];
if(l == r) return insert(rt->treap , val , y), void();
ll mid = (l+r)>>1;
if(x <= mid) modify(l , mid , x , y , val , rt->lc);
else modify(mid+1 , r , x , y , val , rt->rc);
//merge treap
if(rt->lc == nullptr && rt->rc == nullptr) insert(rt->treap , val , y);
else if(rt->rc == nullptr) insert(rt->treap , query(rt->lc->treap , y , y , l , r) , y);
else if(rt->lc == nullptr) insert(rt->treap , query(rt->rc->treap , y , y , l , r) , y);
else{
ll a = query(rt->lc->treap , y , y , l , r) , b = query(rt->rc->treap , y , y , l , r);
insert(rt->treap , __gcd(a , b) , y);
}
}
void init(ll R, ll C) {
r = R, c = C;
}
void update(ll p, ll q, ll k) {
modify(0 , r-1 , p , q , k , stroot);
}
ll calculate(ll x1, ll y1, ll x2, ll y2) {
return st_query(0 , r-1 , x1 , x2 , y1 , y2 , stroot);
}
// signed main(){
// IOS;
// srand(time(0));
// cin >> r >> c >> n ;
// for(ll i=1 ; i<=n ; ++i){
// //LINE
// ll type ; cin >> type;
// if(type == 1){
// ll p , q , k ; cin >> p >> q >> k ;
// modify(0 , r-1 , p , q , k , stroot);
// }
// else{
// //endl LINE endl
// ll x1 , y1 , x2 , y2;
// cin >> x1 >> y1 >> x2 >> y2;
// ll ans = st_query(0 , r-1 , x1 , x2 , y1 , y2 , stroot);
// cout << ans << '\n';
// //endl LINE endl
// }
// }
// }
