#include<iostream>
#include "game.h"
using namespace std;
/// struct
long long n, m;
long long gcd3(long long a, long long b)
{
// if(!a || !b)return a + b;
if(b > a)swap(a, b);
while(b)
{
long long ost = a % b;
a = b;
b = ost;
}
return a;
}
struct segment_tree_2d
{
struct segment_tree
{
struct node
{
long long val;
node *l;
node *r;
node()
{
val = 0;
l = NULL;
r = NULL;
}
node(long long setval)
{
val = setval;
l = NULL;
r = NULL;
}
};
node *root;
segment_tree *l;
segment_tree *r;
segment_tree()
{
root = new node();
l = NULL;
r = NULL;
}
void merge_nodes(node *tree)
{
if(tree -> l == NULL)tree -> l = new node();
if(tree -> r == NULL)tree -> r = new node();
tree -> val = gcd3(tree -> l -> val, tree -> r -> val);
}
void update(node *tree, long long lt, long long rt, long long updpos, long long updval)
{
if(lt == rt)
{
tree -> val = updval;
return;
}
long long mid = (lt + rt)/2;
if(tree -> l == NULL)tree -> l = new node();
if(tree -> r == NULL)tree -> r = new node();
if(updpos <= mid)update(tree -> l, lt, mid, updpos, updval);
else update(tree -> r, mid+1, rt, updpos, updval);
merge_nodes(tree);
}
long long query(node *tree, long long lt, long long rt, long long ql, long long qr)
{
if(tree == NULL)return 0;
if(qr < lt || ql > rt)return 0;
if(ql <= lt && rt <= qr)
{
return tree -> val;
}
long long mid = (lt + rt)/2;
long long onleft = query(tree -> l, lt, mid, ql, qr);
long long onright = query(tree -> r, mid+1, rt, ql, qr);
return gcd3(onleft, onright);
}
void make_update(long long pos, long long val)
{
update(root, 0, m-1, pos, val);
}
long long make_query(long long ql, long long qr)
{
return query(root, 0, m-1, ql, qr);
}
};
segment_tree *root;
segment_tree_2d()
{
root = new segment_tree();
}
void merge0(segment_tree *tree, long long pos)
{
if(tree -> l == NULL)tree -> l = new segment_tree();
if(tree -> r == NULL)tree -> r = new segment_tree();
long long onleft = tree -> l -> make_query(pos, pos);
long long onright = tree -> r -> make_query(pos, pos);
tree -> make_update(pos, gcd3(onleft, onright));
}
void update(segment_tree *tree, long long lt, long long rt, long long row, long long col, long long updval)
{
if(lt == rt)
{
tree -> make_update(col, updval);
return;
}
long long mid = (lt + rt)/2;
if(row <= mid)
{
if(tree -> l == NULL)tree -> l = new segment_tree();
update(tree -> l, lt, mid, row, col, updval);
}
else
{
if(tree -> r == NULL)tree -> r = new segment_tree();
update(tree -> r, mid+1, rt, row, col, updval);
}
merge0(tree, col);
}
long long query(segment_tree *tree, long long lt, long long rt, long long ql_row, long long qr_row, long long ql_col, long long qr_col)
{
if(tree == NULL)return 0;
if(ql_row > rt || qr_row < lt)return 0;
if(ql_row <= lt && rt <= qr_row)
{
return tree -> make_query(ql_col, qr_col);
}
long long mid = (lt + rt)/2;
long long onleft = query(tree -> l, lt, mid, ql_row, qr_row, ql_col, qr_col);
long long onright = query(tree -> r, mid+1, rt, ql_row, qr_row, ql_col, qr_col);
return gcd3(onleft, onright);
}
void make_update(long long row, long long col, long long updval)
{
update(root, 0, n-1, row, col, updval);
}
long long make_query(long long ql_row, long long qr_row, long long ql_col, long long qr_col)
{
return query(root, 0, n-1, ql_row, qr_row, ql_col, qr_col);
}
};
segment_tree_2d s;
void init(int R, int C)
{
n = R;
m = C;
}
void update(int P, int Q, long long K)
{
// cout << r << " " << c << endl;
s.make_update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
long long ans = s.make_query(P, U, Q, V);
return ans;
}
