#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int N, M;
long long gcd2(long long X, long long Y) {
long long tmp;
while (Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Node1D {
Node1D* left;
Node1D* right;
long long gcd;
};
Node1D* empty1 = new Node1D {NULL, NULL, 0};
struct Node2D {
Node1D* root;
Node2D* left;
Node2D* right;
};
Node2D* empty2 = new Node2D {empty1, NULL, NULL};
Node2D* Root;
Node1D* update2(Node1D* root, Node1D* root1, Node1D* root2, int l, int r, int q, long long val, bool ok) {
if (root == empty1)
root = new Node1D {empty1, empty1, val};
if (l == r) {
if (!ok)
root->gcd = val;
else
root->gcd = gcd2(root1->gcd, root2->gcd);
return root;
}
int mid = (l + r) / 2;
if (q <= mid) {
Node1D* root11 = root1;
Node1D* root12 = root2;
if (root11 != empty1)
root11 = root11->left;
if (root12 != empty1)
root12 = root12->left;
root->left = update2(root->left, root11, root12, l, mid, q, val, ok);
} else {
Node1D* root11 = root1;
Node1D* root12 = root2;
if (root11 != empty1)
root11 = root11->right;
if (root12 != empty1)
root12 = root12->right;
root->right = update2(root->right, root11, root12, mid + 1, r, q, val, ok);
}
if (ok)
root->gcd = gcd2(root1->gcd, root2->gcd);
else
root->gcd = gcd2(root->left->gcd, root->right->gcd);
return root;
}
Node2D* update1(Node2D* root, int l, int r, int p, int q, long long val) {
if (root == empty2)
root = new Node2D {empty1, empty2, empty2};
if (l == r) {
root->root = update2(root->root, root->left->root, root->right->root, 1, M, q, val, 0);
return root;
}
int mid = (l + r) / 2;
if (p <= mid)
root->left = update1(root->left, l, mid, p, q, val);
else
root->right = update1(root->right, mid + 1, r, p, q, val);
root->root = update2(root->root, root->left->root, root->right->root, 1, M, q, val, 1);
return root;
}
long long query2(Node1D* root, int l, int r, int q, int v) {
if (root == empty1)
return 0;
if (v < l || r < q)
return 0;
if (q <= l && r <= v)
return root->gcd;
int mid = (l + r) / 2;
long long val = 0;
if (q <= mid)
val = query2(root->left, l, mid, q, v);
if (mid < v)
val = gcd2(val, query2(root->right, mid + 1, r, q, v));
return val;
}
long long query1(Node2D* root, int l, int r, int p, int q, int u, int v) {
if (root == empty2)
return 0;
if (u < l || r < p)
return 0;
if (p <= l && r <= u)
return query2(root->root, 1, M, q, v);
int mid = (l + r) / 2;
long long val = 0;
if (p <= mid)
val = query1(root->left, l, mid, p, q, u, v);
if (mid < u)
val = gcd2(val, query1(root->right, mid + 1, r, p, q, u, v));
return val;
}
void init(int R, int C) {
Root = empty2;
N = R;
M = C;
}
void update(int P, int Q, long long K) {
Root = update1(Root, 1, N, P + 1, Q + 1, K);
}
long long calculate(int P, int Q, int U, int V) {
return query1(Root, 1, N, P + 1, Q + 1, U + 1, V + 1);
}
