#pragma GCC optimize(2) 
#include <bits/stdc++.h>
#define N 100010
#define lc o << 1
#define rc o << 1 | 1
#define mid ((l + r) >> 1)
#define int long long

using namespace std;

int n, a[N], tot, iv[N];

const int m = 100000;
const int mod = 19961993;

struct Tree {
    int mul;
    bitset <62> arr;
}t[N * 4];

inline void up(int o) {
    t[o].mul = t[lc].mul * t[rc].mul % mod;
    t[o].arr = t[lc].arr | t[rc].arr;
}

inline int power(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
} 

void change(int o, int l, int r, int pos, int val) {
    if(l == r) {
        t[o].mul = val;
        t[o].arr.reset();
        for(int i = 0; i < tot; i++) {
            if(val % a[i] == 0)
                t[o].arr.set(i);
        }
        return;
    }

    if(pos <= mid)
        change(lc, l, mid, pos, val);
    else
        change(rc, mid + 1, r, pos, val);
    up(o);
}

inline int check(int x) {
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0)
            return 0;        
    }
    return 1;
}

bitset <62> tmp;
int res = 1;

void query(int o, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) {
        res = res * t[o].mul % mod;
        tmp |= t[o].arr;
        return;
    }

    if(ql <= mid)
        query(lc, l, mid, ql, qr);
    if(qr > mid)
        query(rc, mid + 1, r, ql, qr);
}

void build(int o, int l, int r) {
    if(l == r) {
        t[o].mul = 3;
        t[o].arr.set(1);
        return;
    }
    build(lc, l, mid);
    build(rc, mid + 1, r);
    up(o);
}

inline int calc() {
    int ans = res;
    for(int i = 0; i < tot; i++) {
        if(tmp.test(i))
            ans = ans * (a[i] - 1) % mod * iv[i] % mod;
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;

    for(int i = 2; i <= 281; i++) {
        if(check(i))
            a[tot++] = i, iv[tot - 1] = power(a[tot - 1], mod - 2);
    }

    build(1, 1, m);

    while(T--) {
        int op;
        cin >> op;
        if(op == 0) {
            int l, r;
            cin >> l >> r;
            tmp.reset();
            res = 1;
            query(1, 1, m, l, r);
            printf("%lld\n", calc());
        } else {
            int pos, val;
            cin >> pos >> val;
            change(1, 1, m, pos, val);
        }
    }
}