#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
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;
}
struct segtree{
struct Node{
ll v,flag;
Node* l, *r;
Node(ll a, Node* _l, Node* _r) : v(a), l(_l), r(_r){
flag = -1;
}
};
int size;
Node* root, *null;
void init(int n){
size = 1;
while(size < n) size*=2;
null = new Node(0, nullptr, nullptr);
null->l = null->r = null;
root = null;
}
Node *update(Node* node, int l, int r, int i, ll v){
if(node == null) node = new Node(0, null, null);
if(l+1 == r){
node->v = v;
return node;
}
int mid = (l + r) / 2;
if(node->flag==-1 || node->flag == i){
node->flag = i;
node->v = v;
return node;
}
else if(node->flag != -2){
if(node->flag < mid)
node->l = update(node->l, l, mid, node->flag, node->v);
else
node->r = update(node->r, mid, r, node->flag, node->v);
node->flag = -2;
}
if(i < mid){
node->l = update(node->l, l, mid, i, v);
}
else
node->r = update(node->r, mid, r, i, v);
node->v = gcd2(node->l->v, node->r->v);
return node;
}
void update(int i, ll v){
root = update(root, 0, size, i, v);
}
ll query(Node* node, int l, int r, int L, int R){
if(l >= R || L >= r || node == null) return 0ll;
if(node->flag >= 0){
int pom = node->flag;
if(pom >= l && pom < r) return node->v;
else return 0ll;
}
if(l <= L && R <= r){
ll ret = node->v;
return ret;
}
int mid = (L + R) / 2;
ll left = query(node->l, l, r, L, mid);
ll right = query(node->r, l, r, mid, r);
return gcd2(left, right);
}
ll query(int l, int r){
return query(root, l, r, 0, size);
}
};
struct seg2D{
struct Node{
segtree col;
Node*l , *r;
Node(int sz, Node* a, Node* b) : l(a), r(b){ col.init(sz);}
};
Node* root, *null;
int row_size, col_size;
void init(int n, int m){
row_size = 1;
while(row_size<n) row_size*=2;
col_size = m;
null = new Node(col_size, nullptr, nullptr);
null->l= null->r = null;
root = null;
}
ll query(Node* node, int l1, int r1, int l2, int r2, int L, int R){
if(l1 >= R || L >= r1 || node == null) return 0ll;
if(l1 <= L && R <= r1){
return node->col.query(l2, r2);
}
int mid = (L + R) / 2;
ll left = query(node->l, l1, r1, l2, r2, L, mid);
ll right = query(node->r, l1, r1, l2, r2, mid, R);
return gcd2(left, right);
}
ll query(int l1, int r1, int l2, int r2){
return query(root, l1, r1, l2, r2, 0, row_size);
}
Node* update(Node* node, int l, int r, int L, int R, ll v){
if (node == null) node = new Node(col_size, null, null);
if (L+1==R) {
node->col.update(r, v);
return node;
}
int mid = (L + R) / 2;
if (l < mid) {
node->l = update(node->l, l, r, L, mid, v);
}
else {
node->r = update(node->r, l, r, mid, R, v);
}
ll new_v = gcd2(node->l->col.query(r, r + 1), node->r->col.query(r, r + 1));
node->col.update(r, new_v);
return node;
}
void update(int l, int r, ll v){
root = update(root, l, r, 0, row_size, v);
}
};
seg2D mat;
void init(int R, int C) {
mat.init(R, C);
}
void update(int P, int Q, long long K) {
mat.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return mat.query(P, U+1, Q, V+1);
}
