#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
const int offset = 1 << 30;
const int MAX_ROW = 1e6;
const int MAX_COL = 1 << 24;
int row_root;
int root[MAX_ROW], l[MAX_ROW], r[MAX_ROW];
unsigned char left_child[3 * MAX_COL], right_child[3 * MAX_COL];
ll num[MAX_COL];
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
void create_col(int &node) {
static int sz;
if (!node)
node = ++sz;
}
void create_row(int &node) {
static int sz;
if (!node) {
node = ++sz;
create_col(root[node]);
}
}
void init(int R, int C) {
create_row(row_root);
}
void write(unsigned char* ptr, int val) {
*ptr = val & 255;
*(ptr + 1) = val >> 8 & 255;
*(ptr + 2) = val >> 16 & 255;
}
int get(unsigned char* ptr) {
return *ptr | *(ptr + 1) << 8 | *(ptr + 2) << 16;
}
int get_left(int x) {
return get(left_child + 3 * x);
}
int get_right(int x) {
return get(right_child + 3 * x);
}
void update_col(int x, int lo, int hi, int lft, int rig, int col, ll val) {
if (hi - lo == 1) {
num[x] = lft || rig ? gcd(num[lft], num[rig]) : val;
return;
}
int mid = (lo + hi) / 2;
if (col < mid) {
int tmp = get_left(x);
create_col(tmp);
write(left_child + 3 * x, tmp);
update_col(tmp, lo, mid, get_left(lft), get_left(rig), col, val);
}
else {
int tmp = get_right(x);
create_col(tmp);
write(right_child + 3 * x, tmp);
update_col(tmp, mid, hi, get_right(lft), get_right(rig), col, val);
}
num[x] = gcd(num[get_left(x)], num[get_right(x)]);
}
void update_row(int x, int lo, int hi, int row, int col, ll val) {
if (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (row < mid) {
create_row(l[x]);
update_row(l[x], lo, mid, row, col, val);
}
else {
create_row(r[x]);
update_row(r[x], mid, hi, row, col, val);
}
}
update_col(root[x], 0, offset, root[l[x]], root[r[x]], col, val);
}
void update(int p, int q, ll k) {
update_row(row_root, 0, offset, p, q, k);
}
ll query_col(int x, int lo, int hi, int from, int to) {
if (!x || lo >= to || hi <= from)
return 0;
if (lo >= from && hi <= to)
return num[x];
int mid = (lo + hi) / 2;
return gcd(query_col(get_left(x), lo, mid, from, to), query_col(get_right(x), mid, hi, from, to));
}
ll query_row(int x, int lo, int hi, int from, int to, int col1, int col2) {
if (!x || lo >= to || hi <= from)
return 0;
if (lo >= from && hi <= to)
return query_col(root[x], 0, offset, col1, col2);
int mid = (lo + hi) / 2;
return gcd(query_row(l[x], lo, mid, from, to, col1, col2), query_row(r[x], mid, hi, from, to, col1, col2));
}
ll calculate(int p, int q, int u, int v) {
return query_row(row_root, 0, offset, p, u + 1, q, v + 1);
}
