#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define ll long long
struct segtree {
vector<ll> tree;
ll size;
ll n;
ll neutral;
void put(ll i, ll v) {
tree[i]=v;
}
ll combine(ll i, ll j) {
//for min
return __gcd(i,j);
//for max
//return max(i,j);
//for sum
//return i+j;
}
void update(ll x, ll l, ll r, ll i) {
if (i>=r || i<l) return;
if (r-l == 1) return;
ll mid=(l+r)/2;
update(2*x+1,l,mid,i);
update(2*x+2,mid,r,i);
tree[x]=combine(tree[2*x+1],tree[2*x+2]);
}
void update(ll x, ll l, ll r) {
if (r-l == 1) return;
ll mid=(l+r)/2;
update(2*x+1,l,mid);
update(2*x+2,mid,r);
tree[x]=combine(tree[2*x+1],tree[2*x+2]);
}
segtree(vector<ll>&a, ll neutr) {
n=a.size();
//for min
//neutral = inf;
//for max
//neutral = -inf;
//for sum
//neutral = 0;
neutral = neutr;
size=1;
while (size < n) size*=2;
tree.assign(2*size-1,neutral);
for(ll i=0; i<n; ++i) put(size-1+i,a[i]);
update(0,0,size);
}
void clear() {
tree.assign(2*size-1,0);
}
ll calc(ll x, ll lx, ll rx, ll l, ll r) {
if (lx>=r || rx<=l) return neutral;
if (lx>=l && rx<=r) return tree[x];
ll mid=(lx+rx)/2;
ll a=calc(2*x+1,lx,mid,l,r),
b=calc(2*x+2,mid,rx,l,r);
return combine(a,b);
}
ll query(ll l, ll r) {
if (l>=r) return neutral;
return calc(0,0,size,l,r);
}
void set(ll i, ll v) {
put(size-1+i,v);
update(0, 0, size, i);
}
void prll() {
cout<<"TREE: \n";
ll z=0;
while (z<tree.size()) {
for (ll i=z; i<2*z+1; i++) cout<<tree[i]<<' ';
cout<<'\n';
z=z*2+1;
}
cout<<'\n';
}
};
vector<segtree> V;
void init (int r, int c) {
vector<ll> a(c,0);
segtree zero(a,0);
V.assign(r,zero);
}
//map<ll,map<ll,ll>> m;
//set<ll> s;
//map<ll,set<ll>> A;
void update(int x, int y, ll v) {
V[x].set(y,v);
}
ll calculate(int a, int b, int c, int d) {
ll ans=0;
for (ll i=a; i<=c; ++i) {
ans=__gcd(ans,V[i].query(b,d+1));
}
return ans;
}
