#include <bits/stdc++.h>
#include "game.h"
#define ll long long
using namespace std;
struct ColNode
{
ll gcd;
ll LC, RC;
ColNode *L, *R;
ColNode()
{
gcd = LC = RC = 0;
L = R = nullptr;
return;
}
ColNode(ll lc, ll rc)
{
gcd = 0;
LC = lc;
RC = rc;
L = R = nullptr;
return;
}
void Merge()
{
ll l = 0, r = 0;
if(L) l = this->L->gcd;
if(R) r = this->R->gcd;
this->gcd = __gcd(l, r);
return;
}
};
struct RowNode
{
ll gcd;
ll LC, RC;
RowNode *L, *R;
ColNode *col;
RowNode()
{
gcd = LC = RC = 0;
L = R = nullptr;
col = nullptr;
return;
}
RowNode(ll lc, ll rc)
{
gcd = 0;
LC = lc;
RC = rc;
L = R = nullptr;
col = nullptr;
return;
}
}*root;
void init(int R, int C)
{
root = new RowNode(1, 1 << 30);
return;
}
void ColUpdate(int j, ll x, ColNode *node)
{
if(node->LC == node->RC)
{
node->gcd = x;
return;
}
int S = (node->LC + node->RC) >> 1;
if(j <= S)
{
if(!node->L) node->L = new ColNode(node->LC, S);
ColUpdate(j, x, node->L);
}
else
{
if(!node->R) node->R = new ColNode(S + 1, node->RC);
ColUpdate(j, x, node->R);
}
node->Merge();
return;
}
ll ColPoint(int j, ColNode *node)
{
if(!node) return 0;
if(node->LC == node->RC) return node->gcd;
int S = (node->LC + node->RC) >> 1;
if(j <= S)
{
if(!node->L) return 0;
return ColPoint(j, node->L);
}
else
{
if(!node->R) return 0;
return ColPoint(j, node->R);
}
return 0;
}
void Update(int i, int j, ll x, RowNode *node)
{
if(node->LC == node->RC)
{
if(!node->col) node->col = new ColNode(1, 1 << 30);
ColUpdate(j, x, node->col);
return;
}
int S = (node->LC + node->RC) >> 1;
if(i <= S)
{
if(!node->L) node->L = new RowNode(node->LC, S);
Update(i, j, x, node->L);
}
else
{
if(!node->R) node->R = new RowNode(S + 1, node->RC);
Update(i, j, x, node->R);
}
if(!node->col) node->col = new ColNode(1, 1 << 30);
ll l = 0, r = 0;
if(node->L) l = ColPoint(j, node->L->col);
if(node->R) r = ColPoint(j, node->R->col);
ColUpdate(j, __gcd(l, r), node->col);
return;
}
void update(int i, int j, ll x)
{
i++;
j++;
Update(i, j, x, root);
return;
}
ll ColGet(int j, int l, ColNode *node)
{
if(!node) return 0;
if((node->LC > l) || (j > node->RC)) return 0;
if((j <= node->LC) && (node->RC <= l)) return node->gcd;
return __gcd(ColGet(j, l, node->L), ColGet(j, l, node->R));
}
ll Get(int i, int j, int k, int l, RowNode *node)
{
if(!node) return 0;
if((node->LC > k) || (i > node->RC)) return 0;
if((i <= node->LC) && (node->RC <= k))
{
if(!node->col) return 0;
return ColGet(j, l, node->col);
}
return __gcd(Get(i, j, k, l, node->L), Get(i, j, k, l, node->R));
}
ll calculate(int i, int j, int k, int l)
{
i++;
j++;
k++;
l++;
return Get(i, j, k, l, root);
}
//int main()
//{
// int r, c;
// cin >> r >> c;
// init(r, c);
// int t, i, j, l;
// ll k;
// while(true)
// {
// cin >> t >> i >> j >> k;
// if(t == 1) update(i, j, k);
// else
// {
// cin >> l;
// cout << calculate(i, j, k, l) << '\n';
// }
// }
// return 0;
//}
