#include "game.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int lim1 = 30*30*22000+5, lim2 = 30*22000+5;
struct Node{
Node *l, *r;
ll sm;
Node(){
l = nullptr, r = nullptr;
sm = 0;
}
};
Node Nodes[lim1];
int cntNodes = 0;
Node* newNode(){
assert(cntNodes < lim1);
Nodes[cntNodes] = Node();
return &Nodes[cntNodes++];
}
struct sparse_segtree{
int n;
Node* root = nullptr;
sparse_segtree(){}
sparse_segtree(int _n){
n = _n;
root = newNode();
}
void upd(Node *nd, int l, int r, int in, ll x){
if(l != r){
if(in <= (l+r)/2){
if(!nd->l) nd->l = newNode();
upd(nd->l, l, (l+r)/2, in, x);
}
else{
if(!nd->r) nd->r = newNode();
upd(nd->r, (l+r)/2+1, r, in, x);
}
nd->sm = 0;
if(nd->l) nd->sm = __gcd(nd->sm, nd->l->sm);
if(nd->r) nd->sm = __gcd(nd->sm, nd->r->sm);
}
else nd->sm = x;
}
void upd(int in, ll x){
upd(root, 0, n-1, in, x);
}
ll sum(Node* nd, int L, int R, int l, int r){
if(L > r || R < l) return 0;
if(L >= l && R <= r) return nd->sm;
int md = (L+R)/2;
ll rt = 0;
if(nd->l) rt = __gcd(rt, sum(nd->l, L, md, l, r));
if(nd->r) rt = __gcd(rt, sum(nd->r, md+1, R, l, r));
return rt;
}
ll sum(int l, int r){
return sum(root, 0, n-1, l, r);
}
ll get(Node *nd, int l, int r, int in){
if(l == r) return nd->sm;
if(in <= (l+r)/2) return (nd->l?get(nd->l, l, (l+r)/2, in):0);
else return (nd->r?get(nd->r, (l+r)/2+1, r, in):0);
}
ll get(int in){
return get(root, 0, n-1, in);
}
};
struct Node2d{
Node2d *l, *r;
sparse_segtree sm;
Node2d(){}
Node2d(int m){
l = nullptr, r = nullptr;
sm = sparse_segtree(m);
}
};
Node2d Node2ds[lim2];
int cntNode2ds = 0;
Node2d* newNode2d(int m){
assert(cntNode2ds < lim2);
Node2ds[cntNode2ds] = Node2d(m);
return &Node2ds[cntNode2ds++];
}
struct sparse_segtree2d{
int n, m;
Node2d* root;
sparse_segtree2d(int _n, int _m){
n = _n, m = _m;
root = newNode2d(m);
}
void upd(Node2d *nd, int l, int r, int a, int b, ll x){
if(l != r){
if(a <= (l+r)/2){
if(!nd->l) nd->l = newNode2d(m);
upd(nd->l, l, (l+r)/2, a, b, x);
}
else{
if(!nd->r) nd->r = newNode2d(m);
upd(nd->r, (l+r)/2+1, r, a, b, x);
}
ll sm = 0;
if(nd->l) sm = __gcd(sm, nd->l->sm.get(b));
if(nd->r) sm = __gcd(sm, nd->r->sm.get(b));
nd->sm.upd(b, sm);
}
else nd->sm.upd(b, x);
}
void upd(int a, int b, ll x){
upd(root, 0, n-1, a, b, x);
}
ll sum(Node2d* nd, int L, int R, int a1, int b1, int a2, int b2){
if(L > a2 || R < a1) return 0;
if(L >= a1 && R <= a2) return nd->sm.sum(b1, b2);
int md = (L+R)/2;
ll rt = 0;
if(nd->l) rt = __gcd(rt, sum(nd->l, L, md, a1, b1, a2, b2));
if(nd->r) rt = __gcd(rt, sum(nd->r, md+1, R, a1, b1, a2, b2));
return rt;
}
ll sum(int a1, int b1, int a2, int b2){
return sum(root, 0, n-1, a1, b1, a2, b2);
}
};
sparse_segtree2d sp(0, 0);
int updates;
void init(int R, int C){
sp = sparse_segtree2d(R+1, C+1);
}
void update(int P, int Q, long long K) {
updates++;
sp.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
if(P > U) swap(P, U);
if(Q > V) swap(Q, V);
return sp.sum(P, Q, U, V);
}
