#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define MAX_COORD (long long)(1e9)
#define MAX_COORD (long long)(7)
// 1D(only j)
struct Node1D{
Node1D* lc;
Node1D* rc;
int val;
Node1D(){
lc = nullptr;
rc = nullptr;
val = 0;
}
};
void pull1D(Node1D* curr){
int l = (curr->lc == nullptr)?0:curr->lc->val;
int r = (curr->rc == nullptr)?0:curr->rc->val;
curr->val = gcd(l,r);
}
void modify1D(Node1D* curr,int l,int r,int tar,int nv){
if(l == r){
curr->val = nv;
return;
}
int m = (l+r)/2;
if(tar <= m){
// update left
if(curr->lc == nullptr) curr->lc = new Node1D();
modify1D(curr->lc,l,m,tar,nv);
}else{
// update right
if(curr->rc == nullptr) curr->rc = new Node1D();
modify1D(curr->rc,m+1,r,tar,nv);
}
pull1D(curr);
}
int query1D(Node1D* curr,int l,int r,int L,int R){
// cout << l << " " << r << " " << L << " " << R << endl;
if(curr == nullptr)return 0;
if(l == L && r == R){
// cout << "query get: " << curr->val << endl;
return curr->val;
}
int m = (l+r)/2;
if(R <= m){
return query1D(curr->lc,l,m,L,R);
}else if(L >= m+1){
return query1D(curr->rc,m+1,r,L,R);
}else{
return gcd(query1D(curr->lc,l,m,L,m),
query1D(curr->rc,m+1,r,m+1,R));
}
}
// 2D
struct Node{
Node* lc;
Node* rc;
Node1D* val;
Node(){
lc = nullptr;
rc = nullptr;
val = new Node1D();
}
};
void pull(Node1D* curr,Node1D* LN,Node1D* RN,int l,int r,int tarJ){
// cout << "pull rangeJ from " << l << " to " << r << endl;
assert(LN != nullptr || RN != nullptr);
if(LN != nullptr){
}
if(l == r){
int lV = (LN == nullptr)?0:LN->val;
int rV = (RN == nullptr)?0:RN->val;
// cout << "update val:" << lV << " " << rV << ":" << gcd(lV,rV) << endl;
curr->val = gcd(lV,rV);
return;
}
int m = (l+r)/2;
if(tarJ <= m){
if(curr->lc == nullptr)curr->lc = new Node1D();
pull(curr->lc,(LN == nullptr)?nullptr:LN->lc,(RN == nullptr)?nullptr:RN->lc,l,m,tarJ);
}else{
if(curr->rc == nullptr)curr->rc = new Node1D();
pull(curr->rc,(LN == nullptr)?nullptr:LN->rc,(RN == nullptr)?nullptr:RN->rc,m+1,r,tarJ);
}
pull1D(curr);
}
void modify(Node* curr,int li,int ri,int tarI,int tarJ,int nv){
// cout << "modify I in range from " << li << " to " << ri << endl;
if(li == ri){
assert(li == tarI);
modify1D(curr->val,0,MAX_COORD,tarJ,nv);
return;
}
int m = (li+ri)/2;
if(tarI <= m){
if(curr->lc == nullptr)curr->lc = new Node();
modify(curr->lc,li,m,tarI,tarJ,nv);
}else{
if(curr->rc == nullptr)curr->rc = new Node();
modify(curr->rc,m+1,ri,tarI,tarJ,nv);
}
// cout << "pull rangeI(" << li << "," << ri << ")" << endl;
pull(curr->val,(curr->lc == nullptr)?nullptr:curr->lc->val,(curr->rc == nullptr)?nullptr:curr->rc->val,0,MAX_COORD,tarJ);
}
int query(Node* curr,int l,int r,int li,int ri,int lj,int rj){
if(curr == nullptr)return 0;
if(l == li && r == ri){
// cout << "query In " << li << "," << ri << endl;
return query1D(curr->val,0,MAX_COORD,lj,rj);
}
int m = (l+r)/2;
if(ri <= m){
return query(curr->lc,l,m,li,ri,lj,rj);
}else if(li >= m+1){
return query(curr->rc,m+1,r,li,ri,lj,rj);
}else{
return gcd(query(curr->lc,l,m,li,m,lj,rj),
query(curr->rc,m+1,r,m,ri,lj,rj));
}
}
