//
//  main.cpp
//  手写线段树
//
//  Created by SkyWave Sun on 2022/9/26.
//

#include <iostream>
using namespace std;
#define N ((int)1e5 + 1)
int a[N];
long long tree[N << 2];
long long add_tag[N << 2];
long long mul_tag[N << 2];
const int mod = 571373;
void push_up (const int &pos) {
    tree[pos] = (tree[pos << 1] % mod + tree[pos << 1 | 1] % mod) % mod;
}
void push_down(const int &pos,const int &l,const int &r) {
    if (mul_tag[pos] != 1) {
        mul_tag[pos << 1] *= mul_tag[pos] % mod; mul_tag[pos << 1] %= mod;
        tree[pos << 1] *= mul_tag[pos]; tree[pos << 1] %= mod;
        
        mul_tag[pos << 1 | 1] *= mul_tag[pos] % mod; mul_tag[pos << 1 | 1] %= mod;
        tree[pos << 1 | 1] *= mul_tag[pos]; tree[pos << 1 | 1] %= mod;
        
        mul_tag[pos] = 1;
    }
    if (add_tag[pos]) {
        int mid = (l + r) >> 1;
        
        add_tag[pos << 1] += add_tag[pos] % mod; add_tag[pos << 1] %= mod;
        tree[pos << 1] += (mid - l + 1) * add_tag[pos]; tree[pos << 1] %= mod;
        
        add_tag[pos << 1 | 1] += add_tag[pos] % mod; add_tag[pos << 1 | 1] %= mod;
        tree[pos << 1 | 1] += (r - mid) * add_tag[pos]; tree[pos << 1 | 1] %= mod;
        
        add_tag[pos] = 0;
    }
}
void build(const int &l,const int &r,const int &pos) {
    mul_tag[pos] = 1;
    if (l == r) {
        tree[pos] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, pos << 1);
    build(mid + 1, r, pos << 1 | 1);
    push_up(pos);
}
void Add(const int &x,const int &y,const long long &v,const int &l,const int &r,const int &pos) {//x~y + v
    if (x > r || y < l) {
        return;
    }
    if (x <= l && r <= y) {
        add_tag[pos] += v;
        tree[pos] += (r - l + 1) * v;
        return;
    }
    push_down(pos, l, r);
    int mid = (l + r) >> 1;
    Add(x, y, v, l, mid, pos << 1);
    Add(x, y, v, mid + 1, r, pos << 1 | 1);
    push_up(pos);
}
void Mul(const int &x,const int &y,const long long &v,const int &l,const int &r,const int &pos) {//x~y * v
    if (x > r || y < l) {
        return;
    }
    if (x <= l && r <= y) {
        add_tag[pos] *= v; add_tag[pos] %= mod;
        tree[pos] *= v; tree[pos] %= mod;
        mul_tag[pos] *= v; mul_tag[pos] %= mod;
        return;
    }
    push_down(pos, l, r);
    int mid = (l + r) >> 1;
    Mul(x, y, v, l, mid, pos << 1);
    Mul(x, y, v, mid + 1, r, pos << 1 | 1);
    push_up(pos);
}
long long Query(const int &l,const int &r,const int &pos,const int &x,const int &y) {
    if (x > r || y < l) {
        return 0;
    }
    if (x <= l && r <= y) {
        return tree[pos] % mod;
    }
    push_down(pos, l, r);
    int mid = (l + r) >> 1;
    return (Query(l, mid, pos << 1, x, y) % mod + Query(mid + 1, r, pos << 1 | 1, x, y) % mod) % mod;
}
int main(int argc, const char * argv[]) {
    int n,m,rub;
    scanf("%d%d%d",&n,&m,&rub);
    for (int i = 1; i<=n; ++i) {
        scanf("%d",&a[i]);
    }
    build(1, n, 1);
    unsigned char method;
    while (m--) {
        scanf("%hhu",&method);
        if (method == 1) {
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            Mul(x, y, k, 1, n, 1);
        }else if(method == 2) {
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            Add(x, y, k, 1, n, 1);
        }else {
            int x, y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",Query(1, n, 1, x, y));
        }
    }
    return 0;
}

感谢热心又耐心的你看完这篇文章/跳跳