#include <bits/stdc++.h>

using namespace std;
typedef long long nagai;

#include "grader.h"

nagai gcd(nagai a, nagai b)
{
    while (b)
        a = a % b, swap(a, b);
    return a;
}

template<int H>
struct sl
{
    struct nd
    {
        vector<nd*> ri;
        vector<nagai> gcd;
//      vector<int> len;
        pair<int, int> x;
        inline int sz()
        {
            return ri.size();
        }
    };
    nd* header;
    sl()
    {
        header = new nd;
        header->ri.resize(H, nullptr);
        header->gcd.resize(H, 0);
        header->x = {-1, -1};
        //header->len.resize(H, 0);
    }
    nd* last[H];
    int len[H];
    void go(pair<int, int> to)
    {
        nd* cur = header;
        for (int i = H - 1; i >= 0; --i)
        {
            if (cur->ri[i] && cur->ri[i]->x < to)
                cur = cur->ri[i];
            last[i] = cur;
        }
    }
    inline nagai calc(nd* a, nd* b, int i)
    {
        nagai g = a->gcd[i];
        while (!b && a->ri[i] || b && a->ri[i] && a->ri[i]->x < b->x)
            a = a->ri[i], g = gcd(g, a->gcd[i]);
        //cerr << a->x << ' ' << (b ? b->x : -2) << ' ' << i << ' ' << g << endl;
        return g;
    }
    void insert(pair<int, int> ind, nagai val)
    {
        go(ind);
        nd* nw = new nd;
        nw->x = ind;
        for (int i = 0, add = 1; i < H; add &= rand(), ++i)
        {
            if (add)
            {
                if (i > 0)
                {
                    nagai g = calc(last[i], nw, i - 1);
                    nagai g1 = calc(nw, last[i]->ri[i], i - 1);
                    //cerr << "kek " << g << ' ' << last[i]->x << ' ' << last[i]->gcd[i - 1] << endl;
                    last[i]->gcd[i] = g;
                    nw->gcd.push_back(g1);
                }
                else
                    nw->gcd.push_back(val);
                nw->ri.push_back(last[i]->ri[i]);
                last[i]->ri[i] = nw;
            }
            else
            {
                last[i]->gcd[i] = gcd(last[i]->gcd[i], val);
            }
        }
    }
    void erase(pair<int, int> ind)
    {
        go(ind);
        for (int i = 0; i < H; ++i)
        {
            if (last[i]->ri[i] && last[i]->ri[i]->x == ind)
            {
                if (i)
                    last[i]->gcd[i] = calc(last[i], last[i]->ri[i]->ri[i], i - 1);
                last[i]->ri[i] = last[i]->ri[i]->ri[i];
            }
            else
                last[i]->gcd[i] = calc(last[i], last[i]->ri[i], i - 1);
        }
    }
    void print()
    {
        for (int i = 0; i < H; ++i)
        {
            auto v = header;
            while (v)
                cerr << '{' << v->x.first << ',' << v->x.second << '}' << ',' << v->gcd[i] << ' ', v = v->ri[i];
            cerr << endl;
        }
    }
    nagai get(pair<int, int> l, pair<int, int> r)
    {
        nagai g = 0;
        go(l);
        nd* kek = last[0]->ri[0];
        if (!kek)
            return 0;
        //cerr << kek->x.first << ' ' << kek->x.second << endl;
        for (int i = 0; i < H; ++i)
            while (i < kek->sz() && i + 1 >= kek->sz() && kek->ri[i] && kek->ri[i]->x < r)
                g = gcd(g, kek->gcd[i]), kek = kek->ri[i];
        //cerr << kek->x.first << ' ' << kek->x.second << ' ' << g << endl;
        for (int i = H - 1; i >= 0; --i)
            while (i < kek->sz() && kek->ri[i] && kek->ri[i]->x < r)
                g = gcd(g, kek->gcd[i]), kek = kek->ri[i];
        //cerr << kek->x.first << ' ' << kek->x.second << ' ' << g << endl;
        if (kek->x < r)
            g = gcd(g, kek->gcd[0]);
        return g;
    }
};

struct nd
{
    nd* le;
    nd* ri;
    sl<18> skip;
    nd()
        : le(nullptr), ri(nullptr)
    {}
    void children()
    {
        if (!le)
            le = new nd();
        if (!ri)
            ri = new nd();
    }
    void add(int l, int r, int x, int y, nagai val, bool add)
    {
        if (l > x || r <= x)
            return;
        if (add)
            skip.insert({y, x}, val);
        else
            skip.erase({y, x});
        if (r - l == 1)
            return;
        children();
        int m = (l + r) / 2;
        le->add(l, m, x, y, val, add);
        ri->add(m, r, x, y, val, add);
    }
    nagai get(int l, int r, int ql1, int qr1, int ql2, int qr2)
    {
        //skip.print();
        if (l >= qr1 || ql1 >= r)
            return 0;
        if (ql1 <= l && r <= qr1)
            return skip.get({ql2, ql1}, {qr2, ql1});
        children();
        int m = (l + r) / 2;
        return gcd(le->get(l, m, ql1, m, ql2, qr2),
                ri->get(m, r, m, qr1, ql2, qr2));
    }
};

nd* rt = new nd;

int MX = 1000000000;
set<pair<int, int>> p;

void init(int R, int C)
{
    MX = R;
}

void update(int x, int y, long long t)
{
    if (p.count({x, y}))
        rt->add(0, MX, x, y, t, 0);
    rt->add(0, MX, x, y, t, 1);
    p.insert({x, y});
}

long long calculate(int xl, int yl, int xr, int yr)
{
    return rt->get(0, MX, xl, xr + 1, yl, yr + 1);
}