1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <iostream>
  5 #include <algorithm>
  6 
  7 const int MOD=19961993;
  8 const int MAXN=1e5+10;
  9 const int PR_CNT=60;
 10 
 11 int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281};
 12 int inv[]={9980997,13307996,7984798,11406854,14517814,18426456,9393880,5253157,16490343,8260136,2575742,18343454,3895024,17640832,1698894,3013132,7443456,4581442,9236147,18275065,6562848,2779519,7936697,4037258,6379607,19566707,13566404,4104336,3662752,13602421,16661192,1219054,13259427,9047523,3751248,8196316,14621843,1714528,12192356,11884887,8029406,13455046,17976246,13342473,14084859,15548287,10217514,9846724,5364237,3486812,1627803,14950615,1076789,12406658,19340609,8652728,7791857,7955334,1657495,8808852};
 13 
 14 struct Node{
 15     int l;
 16     int r;
 17     Node* lch;
 18     Node* rch;
 19     long long tag;
 20     long long prod;
 21     Node(int,int);
 22     void Maintain();
 23     void Modify(int,long long);
 24     std::pair<long long,long long> Query(int,int);
 25 };
 26 
 27 int main(){
 28     int n,a,b,type;
 29     Node* N=new Node(1,100000);
 30     scanf("%d",&n);
 31     for(int i=0;i<n;i++){
 32         scanf("%d%d%d",&type,&a,&b);
 33         if(type==0){
 34             std::pair<long long,long long> x=N->Query(a,b);
 35             for(int i=0;i<PR_CNT;i++){
 36                 if((x.second&(1ll<<i))!=0){
 37                     (x.first*=inv[i])%=MOD;
 38                 }
 39             }
 40             printf("%lld\n",x.first);
 41         }
 42         else{
 43             N->Modify(a,b);
 44         }
 45     }
 46     return 0;
 47 }
 48 
 49 long long Calc(long long x){
 50     long long ans=0;
 51     for(int i=0;i<PR_CNT;i++){
 52         if(x%prime[i]==0){
 53             ans|=(1ll<<i);
 54         }
 55     }
 56     return ans;
 57 }
 58 
 59 std::pair<long long,long long> Node::Query(int l,int r){
 60     if(l<=this->l&&this->r<=r){
 61         return std::make_pair(this->prod,this->tag);
 62     }
 63     else{
 64         long long p=1;
 65         long long t=0;
 66         std::pair<long long,long long> tmp;
 67         if(l<=this->lch->r){
 68             tmp=this->lch->Query(l,r);
 69             (p*=tmp.first)%=MOD;
 70             t|=tmp.second;
 71         }
 72         if(this->rch->l<=r){
 73             tmp=this->rch->Query(l,r);
 74             (p*=tmp.first)%=MOD;
 75             t|=tmp.second;
 76         }
 77         return std::make_pair(p,t);
 78     }
 79 }
 80 
 81 void Node::Modify(int x,long long d){
 82     if(this->l==this->r){
 83         this->prod=d;
 84         this->tag=Calc(d);
 85     }
 86     else{
 87         if(x<=this->lch->r)
 88             this->lch->Modify(x,d);
 89         else
 90             this->rch->Modify(x,d);
 91         this->Maintain();
 92     }
 93 }
 94 
 95 inline void Node::Maintain(){
 96     this->tag=this->lch->tag|this->rch->tag;
 97     this->prod=this->lch->prod*this->rch->prod%MOD;
 98 }
 99 
100 Node::Node(int l,int r){
101     this->l=l;
102     this->r=r;
103     if(l==r){
104         this->prod=3;
105         this->tag=(1<<1);
106     }
107     else{
108         int mid=(l+r)>>1;
109         this->lch=new Node(l,mid);
110         this->rch=new Node(mid+1,r);
111         this->Maintain();
112     }
113 }