#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 10000, M = 1e5+10, K = 52, MX = 30;
ll gcd(ll x, ll y) { return !y ? x : gcd(y, x % y); }
int rnd() { return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15)); }
struct Node{
Node *L, *R;
int key; int Y; ll val, ans=0ll;
int l, r;
Node() : Y(rand()), key(0), val(0ll), L(nullptr), R(nullptr) {}
Node(int key): key(key), Y(rnd()), val(0ll), L(nullptr), R(nullptr), l(key), r(key) {}
Node(int key, ll val): key(key), Y(rnd()), val(val), ans(val), L(nullptr), R(nullptr), l(key), r(key) {}
void update(){
ans = val;
l = r = key;
if(L) ans = gcd(ans, L->ans), l = min(l, L->l), r = max(r, L->r);
if(R) ans = gcd(ans, R->ans), l = min(l, R->l), r = max(r, R->r);
}
};
typedef Node* Nodep;
struct Treap{
Nodep root;
Treap(){
root = nullptr;
srand(rnd());
}
pair<Nodep, Nodep> split(Nodep v, int pos){
if(!v) return {v, v};
if(v->key >= pos){
auto p = split(v->L, pos);
v->L = p.ss;
v->update();
return {p.ff, v};
}else{
auto p = split(v->R, pos);
v->R = p.ff;
v->update();
return {v, p.ss};
}
}
Nodep merge(Nodep l, Nodep r){
if(!l || !r){
return !l ? r : l;
}
if(l->Y > r->Y){
auto p = merge(l->R, r);
l->R = p;
l->update();
return l;
}else{
auto p = merge(l, r->L);
r->L = p;
r->update();
return r;
}
}
bool find(int pos){
Nodep t = root;
while(t){
if(t->key == pos) return true;
if(t->key > pos) t = t->L;
else t = t->R;
}
return false;
}
void insert(int pos, ll val){
if(find(pos)) update(root, pos, val);
else{
auto p = split(root, pos);
root = merge(merge(p.ff, new Node(pos, val)), p.ss);
}
}
void update(Nodep t, int pos, ll val){
if(t->key == pos){
t->val = val;
t->update();
}else{
if(t->key > pos) update(t->L, pos, val);
else update(t->R, pos, val);
t->update();
}
}
ll query(Nodep v, int l, int r){
if(!v || l > v->r || v->l > r) return 0ll;
if(l <= v->l && v->r <= r) return v->ans;
return gcd(query(v->L, l, r), query(v->R, l, r));
}
ll query(int l, int r){
if(!root) return 0ll;
return query(root, l, r);
}
};
struct SegTree{
Treap treap;
SegTree *l, *r;
int lo, hi;
SegTree(){l=r=nullptr;}
SegTree(int st, int hii){l=r=nullptr; lo=st, hi=hii;}
void new_left(){
if(!l){
l = new SegTree(lo, (lo+hi)>>1);
}
}
void new_right(){
if(!r){
r = new SegTree((lo+hi>>1)+1, hi);
}
}
void calc(int pos){
ll val = 0;
if(l) val = gcd(val, l->treap.query(pos, pos));
if(r) val = gcd(val, r->treap.query(pos, pos));
treap.insert(pos, val);
}
void upd(int x, int y, ll val){
if(lo > x || x > hi) return;
if(lo == hi){
treap.insert(y, val);
return;
}
if(x <= (lo+hi)/2){
new_left();
l->upd(x, y, val);
}else{
new_right();
r->upd(x, y, val);
}
calc(y);
}
ll query(int t, int b, int x, int y){
if(lo > b || t > hi) return 0ll;
if(t <= lo && hi <= b) return treap.query(x, y);
ll ans = 0;
if(l) ans = gcd(ans, l->query(t, (t+b)>>1, x, y));
if(r) ans = gcd(ans, r->query((t+b>>1)+1, b, x, y));
return ans;
}
};
int n, m;
SegTree seg;
void init(int R, int C) {
srand(12341234);
n = R;
m = C;
seg = SegTree(1, n);
}
void update(int P, int Q, long long K) {
++P, ++Q;
seg.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
++P, ++Q, ++U, ++V;
return seg.query(P, U, Q, V);
}
