#include "game.h"
#include <stdlib.h>

typedef long long lld;

static int R,C;

struct X_NODE{
    X_NODE(int s,int e): s(s), e(e), left(NULL), right(NULL), value(0LL) {}
    int s,e;
    X_NODE *left,*right;
    lld value;
};

struct Y_NODE{
    Y_NODE(): left(NULL), right(NULL), xtree(1,C) {}
    Y_NODE *left,*right;
    X_NODE xtree;
} *root;

lld gcd2(lld x,lld y)
{
    if (y == 0) return x;
    return gcd2(y,x%y);
}

void init(int r,int c)
{
    R = r, C = c;
    root = new Y_NODE();
}

void update2(X_NODE *node,int q,lld k)
{
    int s=node->s,e=node->e,m=(s+e)>>1;
    if (s == e){
        node->value = k;
        return;
    }
    X_NODE **child=&(q<=m?node->left:node->right);
    if (*child == NULL){
        *child = new X_NODE(q,q);
        (*child)->value = k;
    }else if ((*child)->s <= q && q <= (*child)->e){
        update2(*child,q,k);
    }else{
        do{
            if (q <= m) e = m;
            else s = m+1;
            m = (s+e)>>1;
        }while ((q<=m) == ((*child)->e <= m));
        X_NODE *nnode=new X_NODE(s,e);
        if ((*child)->e <= m) nnode->left = *child;
        else nnode->right = *child;
        *child = nnode;
        update2(*child,q,k);
    }
    node->value = gcd2(node->left?node->left->value:0,node->right?node->right->value:0);
}

lld query2(X_NODE *node,int s,int e)
{
    if (node == NULL || node->s > e || node->e < s) return 0;
    if (s <= node->s && node->e <= e){
        return node->value;
    }
    return gcd2(query2(node->left,s,e),query2(node->right,s,e));
}

void update1(Y_NODE *node,int s,int e,int p,int q,lld k)
{
    int m=(s+e)>>1;
    if (s == e){
        update2(&node->xtree,q,k);
        return;
    }
    if (p <= m){
        if (node->left == NULL) node->left = new Y_NODE();
        update1(node->left,s,m,p,q,k);
    }else{
        if (node->right == NULL) node->right = new Y_NODE();
        update1(node->right,m+1,e,p,q,k);
    }
    lld v=gcd2(node->left?query2(&node->left->xtree,q,q):0,node->right?query2(&node->right->xtree,q,q):0);
    update2(&node->xtree,q,v);
}

void update(int p,int q,lld k)
{
    ++p, ++q;
    update1(root,1,R,p,q,k);
}

lld query1(Y_NODE *node,int s,int e,int p,int q,int u,int v)
{
    if (node == NULL || s > u || e < p) return 0;
    if (p <= s && e <= u) return query2(&node->xtree,q,v);
    int m=(s+e)>>1;
    return gcd2(query1(node->left,s,m,p,q,u,v),query1(node->right,m+1,e,p,q,u,v));
}

lld calculate(int p,int q,int u,int v)
{
    ++p, ++q, ++u, ++v;
    return query1(root,1,R,p,q,u,v);
}