1 #include <iostream>
  2 #include <cstdio>
  3 using namespace std;
  4 
  5 typedef long long ll;
  6 const ll MAXN=100010;
  7 const ll MOD=571373;
  8 
  9 struct Tree
 10 {
 11     ll l,r;
 12     ll sum;
 13     ll atag;
 14     ll mtag;
 15 }t[MAXN<<2];
 16 ll a[MAXN<<2];
 17 
 18 ll cnt=0;
 19 void buildTree(ll root,ll l,ll r)   //建树
 20 {
 21     t[root].l=l,t[root].r=r;
 22     if (l==r) t[root].sum=a[++cnt];
 23     else
 24     {
 25         ll mid=(l+r)>>1;
 26         buildTree(root<<1,l,mid);
 27         buildTree(root<<1|1,mid+1,r);
 28         t[root].sum=(t[root<<1].sum+t[root<<1|1].sum)%MOD;
 29     }
 30     return;
 31 }
 32 
 33 void pushDown(ll root)   //下传标记
 34 {
 35     t[root<<1].sum=(t[root].mtag*t[root<<1].sum+((t[root<<1].r-t[root<<1].l+1)*t[root].atag)%MOD)%MOD;
 36     t[root<<1|1].sum=(t[root].mtag*t[root<<1|1].sum+((t[root<<1|1].r-t[root<<1|1].l+1)*t[root].atag)%MOD)%MOD;
 37     t[root<<1].mtag=(t[root<<1].mtag*t[root].mtag)%MOD;
 38     t[root<<1|1].mtag=(t[root<<1|1].mtag*t[root].mtag)%MOD;
 39     t[root<<1].atag=(t[root<<1].atag*t[root].mtag+t[root].atag)%MOD;
 40     t[root<<1|1].atag=(t[root<<1|1].atag*t[root].mtag+t[root].atag)%MOD;
 41     t[root].mtag=1;
 42     t[root].atag=0;
 43     return;
 44 }
 45 void mul(ll root,ll l,ll r,ll val)   //区间修改*
 46 {
 47     if (t[root].r<l || t[root].l>r) return;
 48     if (t[root].l>=l && t[root].r<=r)
 49     {
 50         t[root].sum=t[root].sum*val%MOD;
 51         t[root].atag=t[root].atag*val%MOD;
 52         t[root].mtag=t[root].mtag*val%MOD;
 53         return;
 54     }
 55     if (t[root].mtag!=1 || t[root].atag!=0) pushDown(root);
 56     mul(root<<1,l,r,val),mul(root<<1|1,l,r,val);
 57     t[root].sum=(t[root<<1].sum+t[root<<1|1].sum)%MOD;
 58     return;
 59 }
 60 
 61 void add(ll root,ll l,ll r,ll val)   //区间修改+
 62 {
 63     if (t[root].r<l || t[root].l>r) return;
 64     if (t[root].l>=l && t[root].r<=r)
 65     {
 66         t[root].sum=(t[root].sum+val*(t[root].r-t[root].l+1))%MOD;
 67         t[root].atag=(t[root].atag+val)%MOD;
 68         return;
 69     }
 70     if (t[root].mtag!=1 || t[root].atag!=0) pushDown(root);
 71     add(root<<1,l,r,val),add(root<<1|1,l,r,val);
 72     t[root].sum=(t[root<<1].sum+t[root<<1|1].sum)%MOD;
 73     return;
 74 }
 75 
 76 ll query(ll root,ll l,ll r)
 77 {
 78     if (t[root].r<l || t[root].l>r) return 0;
 79     if (t[root].l>=l && t[root].r<=r) return t[root].sum;
 80     if (t[root].mtag!=1 || t[root].atag!=0) pushDown(root);
 81     return (query(root<<1,l,r)+query(root<<1|1,l,r))%MOD;
 82 }
 83 
 84 int main()
 85 {
 86     ll n,m,p;
 87     scanf("%lld%lld%lld",&n,&m,&p);
 88     for (ll i=1;i<=n;i++) scanf("%lld",&a[i]);
 89     for (ll i=0;i<MAXN<<2;i++) t[i].sum=t[i].atag=0,t[i].mtag=1;   //init
 90 
 91     buildTree(1,1,n);
 92 
 93     while (m--)
 94     {
 95         ll opt;
 96         scanf("%lld",&opt);
 97         ll x,y,k;
 98         if (opt==1)
 99         {
100             scanf("%lld%lld%lld",&x,&y,&k);
101             mul(1,x,y,k);
102         }
103         else if (opt==2)
104         {
105             scanf("%lld%lld%lld",&x,&y,&k);
106             add(1,x,y,k);
107         }
108         else if (opt==3)
109         {
110             scanf("%lld%lld",&x,&y);
111             printf("%lld\n",query(1,x,y));
112         }
113     }
114 
115     return 0;
116 }