#include "game.h"
#include <bits/stdc++.h>
using namespace std;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
#define int long long
struct node{
node* l, *r;
int val;
};
void Build(node *root, int left, int right){
if(left == right){
return;
}
root->l = new node{NULL,NULL,0};
root->r = new node{NULL,NULL,0};
int mid = (left+right)/2;
Build(root->l, left, mid);
Build(root->r, mid+1, right);
}
int Update(node *root, int left, int right, int qL, int qR, int val){
if(left > qR || right < qL) return root->val;
if(left >= qL && right <= qR){
root->val = val;
return val;
}
int mid = (left+right)/2;
return root->val = gcd2(Update(root->l, left, mid, qL, qR, val), Update(root->r, mid+1, right, qL, qR, val));
}
int query(node *root, int left, int right, int qL, int qR){
if(left > qR || right < qL){
return 0;
}
if(left >= qL && right <= qR){
return root->val;
}
int mid = (left+right)/2;
return gcd2(query(root->l, left, mid, qL, qR), query(root->r, mid+1, right, qL, qR));
}
vector< node* > roots;
int r, c;
#undef int
void init(int R, int C) {
#define int long long
r = R, c = C;
roots.resize(R+1);
for(int i = 1; i <= R; i++){
roots[i] = new node{NULL,NULL,0};
Build(roots[i], 1, C);
}
#undef int
}
void update(int P, int Q, long long K) {
#define int long long
Update(roots[P+1], 1, c, Q+1, Q+1, K);
#undef int
}
long long calculate(int P, int Q, int U, int V) {
#define int long long
int gcd = 0;
for(int i = P+1; i <= U+1; i++){
gcd = gcd2(gcd, query(roots[i], 1, c, Q+1, V+1));
}
return gcd;
#undef int
}
