int t[maxn * 4];
vi a(maxn);
void build(int v, int l, int r) {
    if (l + 1 == r) {
        t[v] = a[l];
        return;
    }
    int m = (l + r) / 2, v1 = 2 * v + 1, v2 = 2 * v + 2;
    build(v1, l, m);
    build(v2, m, r);
    t[v] = gcd(t[v1], t[v2]);
}
void upd(int v, int l, int r, int pos, int x) {
    if (l + 1 == r) {
        a[l] = x;
        t[v] = x;
        return;
    }
    int m = (l + r) / 2, v1 = 2 * v + 1, v2 = 2 * v + 2;
    if (pos < m)
        upd(v1, l, m, pos, x);
    else
        upd(v2, m, r, pos, x);
    t[v] = gcd(t[v1], t[v2]);
}
int get(int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return t[v];
    if (l >= qr || r <= ql) return 0;
    int m = (l + r) / 2, v1 = 2 * v + 1, v2 = 2 * v + 2;
    int g1 = get(v1, l, m, ql, qr);
    int g2 = get(v2, m, r, ql, qr);
    return gcd(g1, g2);
}