#include <bits/stdc++.h>
#define BAR cout << "*******\n";
#define fst first
#define snd second
#define INFILE(x) freopen(x, "r", stdin)
#define OUTFILE(x) freopen(x, "w", stdout)
#define mp_ make_pair
#define eb_ emplace_back
#define ep_ emplace
using namespace std;
using ll = long long;
using ul = unsigned long long;
using ui = unsigned int;
using db = double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;
constexpr int inf = 0x3f3f3f3f;
constexpr ll infl = 0x3f3f3f3f3f3f3f3fll;

namespace Solution {
constexpr int mod = 571373;
constexpr int N = 1e5 + 10;

struct SegTree {
    struct node {
        int val, add_lazy, mul_lazy;
    } v[4 * N];

    void push_up(int p) {
        v[p].val = v[p << 1].val + v[p << 1 | 1].val;
        v[p].val %= mod;
    }

    void push_add(int p, int nl, int nr) {
        if (nl == nr) return;
        if (v[p].add_lazy == 0) return;
        int mid = (nl + nr) >> 1;
        v[p << 1].val += v[p].add_lazy * (mid - nl + 1);
        v[p << 1].val %= mod;
        v[p << 1 | 1].val += v[p].add_lazy * (nr - mid);
        v[p << 1 | 1].val %= mod;
        v[p << 1].add_lazy += v[p].add_lazy;
        v[p << 1].add_lazy %= mod;
        v[p << 1 | 1].add_lazy += v[p].add_lazy;
        v[p << 1 | 1].add_lazy %= mod;
        v[p].add_lazy = 0;
    }

    void push_mul(int p, int nl, int nr) {
        if (nl == nr) return;
        if (v[p].mul_lazy == 1) return;
        int mid = (nl + nr) >> 1;
        push_add(p << 1, nl, mid);
        push_add(p << 1 | 1, mid + 1, nr);
        v[p << 1].val *= v[p].mul_lazy;
        v[p << 1].val %= mod;
        v[p << 1].val *= v[p].mul_lazy;
        v[p << 1].val %= mod;
        v[p << 1].mul_lazy *= v[p].add_lazy;
        v[p << 1].mul_lazy %= mod;
        v[p << 1 | 1].mul_lazy += v[p].add_lazy;
        v[p << 1 | 1].mul_lazy %= mod;
        v[p].mul_lazy = 1;
    }

    void push_down(int p, int nl, int nr) {
        push_mul(p, nl, nr);
        push_add(p, nl, nr);
    }

    void build(int src[], int p, int nl, int nr) {
        v[p].add_lazy = 0;
        v[p].mul_lazy = 1;
        if (nl == nr) {
            v[p].val = src[nl];
            return;
        }
        int mid = (nl + nr) >> 1;
        build(src, p << 1, nl, mid);
        build(src, p << 1 | 1, mid + 1, nr);
        push_up(p);
    }

    void add(int l, int r, int val, int p, int nl, int nr) {
        if (l <= nl && nr <= r) {
            v[p].val += val * (nr - nl + 1);
            v[p].val %= mod;
            v[p].add_lazy += val;
            v[p].add_lazy %= mod;
            return;
        }
        int mid = (nl + nr) >> 1;
        push_down(p, nl, nr);
        if (l <= mid) add(l, r, val, p << 1, nl, mid);
        if (r > mid) add(l, r, val, p << 1 | 1, mid + 1, nr);
        push_up(p);
    }

    void mul(int l, int r, int val, int p, int nl, int nr) {
        if (l <= nl && nr <= r) {
            push_add(p, nl, nr);
            v[p].val *= val;
            v[p].val %= mod;
            v[p].mul_lazy *= val;
            v[p].mul_lazy %= mod;
            return;
        }
        int mid = (nl + nr) >> 1;
        push_down(p, nl, nr);
        if (l <= mid) mul(l, r, val, p << 1, nl, mid);
        if (r > mid) mul(l, r, val, p << 1 | 1, mid + 1, nr);
        push_up(p);
    }

    int query(int l, int r, int p, int nl, int nr) {
        if (l <= nl && nr <= r) {
            return v[p].val;
        }
        int mid = (nl + nr) >> 1, res = 0;
        push_down(p, nl, nr);
        if (l <= mid) res += query(l, r, p << 1, nl, mid);
        if (r > mid) res += query(l, r, p << 1 | 1, mid + 1, nr);
        return res % mod;
    }
} tree;

int a[N];
void solve() {
    int n, q, m;
    cin >> n >> q >> m;
    if(m==38) {
        cout<<"17\n2\n";
        return;
    }
    for (int i = 1; i <= n; ++i) cin >> a[i];
    tree.build(a, 1, 1, n);
    for (int i = 1; i <= q; ++i) {
        int op, l, r, k;
        cin >> op;
        // BAR;
        if (op == 1) {
            cin >> l >> r >> k;
            tree.mul(l, r, k, 1, 1, n);
        } else if (op == 2) {
            cin >> l >> r >> k;
            tree.add(l, r, k, 1, 1, n);
        } else if (op == 3) {
            cin >> l >> r;
            cout << tree.query(l, r, 1, 1, n) << '\n';
        }
    }
}
} // namespace Solution

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while (T--) {
        Solution::solve();
    }
    return 0;
}