#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int R, C;
long long gcd2(long long X, long long Y) {
if(!X) return Y;
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct ST{
struct Node{
int l=0, r=0;
ll v=0;
};
ll v;
int x, s, e;
vector<Node> node;
void update(int nn, int ns, int ne){
if(ns>x || ne<x) return;
if(ns==ne){
node[nn].v = v;
return;
}
int m = ns+ne>>1;
if(m<x){
if(!node[nn].r) node[nn].r = node.size(), node.resize(node[nn].r+1);
update(node[nn].r, m+1, ne);
}
else{
if(!node[nn].l) node[nn].l = node.size(), node.resize(node[nn].l+1);
update(node[nn].l, ns, m);
}
node[nn].v = gcd2(node[nn].l?node[node[nn].l].v:0ll, node[nn].r?node[node[nn].r].v:0ll);
}
void update(int a, ll b){
tie(x, v) = tie(a, b);
update(0, 0, C);
}
ll query(int nn, int ns, int ne){
if(ns>e || ne<s) return 0;
if(s<=ns && ne<=e) return node[nn].v;
int m = ns+ne>>1;
return gcd2(node[nn].l?query(node[nn].l, ns, m):0ll, node[nn].r?query(node[nn].r, m+1, ne):0ll);
}
ll query(int a, int b){
tie(s, e) = tie(a, b);
return query(0, 0, C);
}
};
struct ST2{
struct Node{
int l=0, r=0;
ST v;
};
ll v;
int x, xx, s, e, ss, ee;
vector<Node> node;
void update(int nn, int ns, int ne){
if(ns>x || ne<x) return;
if(ns==ne){
node[nn].v.update(xx, v);
return;
}
int m = ns+ne>>1;
if(m<x){
if(!node[nn].r) node[nn].r = node.size(), node.resize(node[nn].r+1), node[node[nn].r].v.node.resize(1);
update(node[nn].r, m+1, ne);
}
else{
if(!node[nn].l) node[nn].l = node.size(), node.resize(node[nn].l+1), node[node[nn].l].v.node.resize(1);
update(node[nn].l, ns, m);
}
node[nn].v.update(xx, gcd2(node[nn].l?node[node[nn].l].v.query(xx, xx):0ll, node[nn].r?node[node[nn].r].v.query(xx, xx):0ll));
}
void update(int a, int b, ll c){
tie(x, xx, v) = tie(a, b, c);
update(0, 0, R);
}
ll query(int nn, int ns, int ne){
if(ns>e || ne<s) return 0;
if(s<=ns && ne<=e) return node[nn].v.query(ss, ee);
int m = ns+ne>>1;
return gcd2(node[nn].l?query(node[nn].l, ns, m):0ll, node[nn].r?query(node[nn].r, m+1, ne):0ll);
}
ll query(int a, int b, int c, int d){
tie(s, e, ss, ee) = tie(a, b, c, d);
return query(0, 0, R);
}
} seg;
void init(int R_, int C_) {
R = R_ - 1, C = C_ - 1;
seg.node.resize(1);
seg.node[0].v.node.resize(1);
}
void update(int P, int Q, ll K) {
seg.update(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return seg.query(P, U, Q, V);
}
