#include "game.h"
#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long tree[4*2005][4*2005];
long long tree2[4*10][4*100005];
long long nzd(long long a, long long b) {
if (b==0) return a;
return nzd(b, a%b);
}
long long query_y(int kx, int ky, int left, int right, int levo_kol, int desno_kol) {
if (m<=2000) {
if (left>=levo_kol && right<=desno_kol)
return tree[kx][ky];
else if (left>desno_kol || right<levo_kol)
return 0;
int mid=(left+right)/2;
long long r1=query_y(kx, 2*ky, left, mid, levo_kol, desno_kol);
long long r2=query_y(kx, 2*ky+1, mid+1, right, levo_kol, desno_kol);
return nzd(r1, r2);
}
else {
if (left>=levo_kol && right<=desno_kol)
return tree2[kx][ky];
else if (left>desno_kol || right<levo_kol)
return 0;
int mid=(left+right)/2;
long long r1=query_y(kx, 2*ky, left, mid, levo_kol, desno_kol);
long long r2=query_y(kx, 2*ky+1, mid+1, right, levo_kol, desno_kol);
return nzd(r1, r2);
}
}
long long query_x(int k, int left, int right, int gore_red, int dole_red, int levo_kol, int desno_kol) {
if (left>=gore_red && right<=dole_red)
return query_y(k, 1, 0, m-1, levo_kol, desno_kol);
else if (left>dole_red || right<gore_red)
return 0;
int mid=(left+right)/2;
long long r1=query_x(2*k, left, mid, gore_red, dole_red, levo_kol, desno_kol);
long long r2=query_x(2*k+1, mid+1, right, gore_red, dole_red, levo_kol, desno_kol);
return nzd(r1, r2);
}
void update_y(int kx, int left_x, int right_x, int ky, int left_y, int right_y, int row, int col, long long val) {
if (m<=2000) {
if (left_y==right_y) {
if (left_x==right_x)
tree[kx][ky]=val;
else
tree[kx][ky]=nzd(tree[2*kx][ky], tree[2*kx+1][ky]);
}
else {
int mid=(left_y+right_y)/2;
if (col>mid)
update_y(kx, left_x, right_x, 2*ky+1, mid+1, right_y, row, col, val);
else
update_y(kx, left_x, right_x, 2*ky, left_y, mid, row, col, val);
tree[kx][ky]=nzd(tree[kx][2*ky], tree[kx][2*ky+1]);
}
}
else {
if (left_y==right_y) {
if (left_x==right_x)
tree2[kx][ky]=val;
else
tree2[kx][ky]=nzd(tree2[2*kx][ky], tree2[2*kx+1][ky]);
}
else {
int mid=(left_y+right_y)/2;
if (col>mid)
update_y(kx, left_x, right_x, 2*ky+1, mid+1, right_y, row, col, val);
else
update_y(kx, left_x, right_x, 2*ky, left_y, mid, row, col, val);
tree2[kx][ky]=nzd(tree2[kx][2*ky], tree2[kx][2*ky+1]);
}
}
}
void update_x(int k, int left, int right, int row, int col, long long val) {
if (left!=right) {
int mid=(left+right)/2;
if (row>mid) update_x(2*k+1, mid+1, right, row, col, val);
else update_x(2*k, left, mid, row, col, val);
}
update_y(k, left, right, 1, 0, m-1, row, col, val);
}
void init(int r, int c) {
n=r, m=c;
}
void update(int r, int c, long long br) {
update_x(1, 0, n-1, r, c, br);
}
long long calculate(int x1, int y1, int x2, int y2) {
long long rez=query_x(1, 0, n-1, x1, x2, y1, y2);
return rez;
}
