#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;
Node* l, * r;
int flag;
Node(ll a, Node* b, Node* c) : v(a), l(b), r(c) {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 lx, int rx, int i, ll v) {
if (node == null)
node = new Node(0, null, null);
if (lx == rx - 1) {
node->v = v;
return node;
}
int mid = (lx + rx) / 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, lx, mid, node->flag, node->v);
}
else {
node->r =update(node->r, mid, rx,node->flag, node->v);
}
node->flag = -2;
}
if (i < mid) {
node->l = update(node->l, lx, mid, i, v);
}
else {
node->r = update(node->r, mid, rx, 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 lx, int rx, int l, int r) {
if (l >= rx || lx >= r || node == null) {
return 0ll;
}
if (node->flag >= 0) {
int p = node->flag;
if (p >= l && p < r)
return node->v;
else
return 0LL;
}
if (l <= lx && rx <= r) {
ll ret = node->v;
return ret;
}
int mid = (lx + rx) / 2;
ll left = query(node->l, lx, mid, l, r);
ll right = query(node->r, mid, rx, l, r);
return gcd2(left, right);
}
ll query(int l, int r) {
return query(root, 0, size, l, r);
}
};
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);
}
