#include <bits/stdc++.h>
#define ll long long
#define M 571373
using namespace std;

class SegTree {
    vector<ll> tree, lazy, nazy;
    int n, root, end;

    void push_down(int s, int t, int p) {
        if (s != t) {
            int m = s + (t - s) / 2;

            // 处理懒惰标记
            
            if (nazy[p] != 1) {
            	nazy[2 * p] =nazy[p];
            	nazy[2 * p + 1]=nazy[p];
                tree[2 * p] *= nazy[p];
                tree[2 * p] %=M;
                tree[2 * p + 1] *= nazy[p];
                tree[2 * p + 1] %=M;
                nazy[p] = 1;
            }
            if (lazy[p] != 0) {
                lazy[2 * p] += lazy[p];
                lazy[2 * p + 1] += lazy[p];
                tree[2 * p] += lazy[p] * (m - s + 1);
                tree[2 * p] %=M;
                tree[2 * p + 1] += lazy[p] * (t - m);
                tree[2 * p + 1] %=M;
                lazy[p] = 0;
            }
  
            
        }
    }

    void range_add(int l, int r, int v, int s, int t, int p) {
        if (l <= s && r >= t) {
            tree[p] += v * (t - s + 1);
            tree[p] %=M;
            lazy[p] += v;
            lazy[p] %=M;
            return;
        }
        push_down(s, t, p);
        int m = s + (t - s) / 2;
        if (l <= m) range_add(l, r, v, s, m, 2 * p);
        if (r > m) range_add(l, r, v, m + 1, t, 2 * p + 1);
        tree[p] = tree[2 * p] + tree[2 * p + 1];
        tree[p]%= M;
    }

    void range_mul(int l, int r, int v, int s, int t, int p) {
        if (l <= s && r >= t) {
            tree[p] *= v;
            tree[p]%= M;
            lazy[p] *= v; // 更新加法的懒惰标记
            lazy[p]%=M;
            nazy[p] *= v;
            nazy[p] %=M;
            return;
        }
        push_down(s, t, p);
        int m = s + (t - s) / 2;
        if (l <= m) range_mul(l, r, v, s, m, 2 * p);
        if (r > m) range_mul(l, r, v, m + 1, t, 2 * p + 1);
        tree[p] = tree[2 * p] + tree[2 * p + 1];
        tree[p]%= M;
    }

    ll range_sum(int l, int r, int s, int t, int p) {
        if (l <= s && r >= t) return tree[p];
        push_down(s, t, p);
        int m = s + (t - s) / 2;
        ll sum = 0;
        if (l <= m) sum += range_sum(l, r, s, m, 2 * p);
        if (r > m) sum += range_sum(l, r, m + 1, t, 2 * p + 1);
        return sum%M;
    }

    void build(const vector<int>& arr, int s, int t, int p) {
        if (s == t) {
            tree[p] = arr[s];
            return;
        }
        int m = s + (t - s) / 2;
        build(arr, s, m, 2 * p);
        build(arr, m + 1, t, 2 * p + 1);
        tree[p] = tree[2 * p] + tree[2 * p + 1];
    }

public:
    SegTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n, 0);
        lazy.resize(4 * n, 0);
        nazy.resize(4 * n, 1);
        root = 1;
        end = n - 1;
        build(arr, 0, end, root);
    }

    void range_add(int l, int r, int v) {
        range_add(l, r, v, 0, end, root);
    }

    void range_mul(int l, int r, int v) {
        range_mul(l, r, v, 0, end, root);
    }

    ll range_sum(int l, int r) {
        return range_sum(l, r, 0, end, root);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q, m;
    cin >> n >> q >> m;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    SegTree segTree(v);

    while (q--) {
        int c;
        cin >> c;
        if (c == 2) {
            int x, y, k;
            cin >> x >> y >> k;
            segTree.range_add(x - 1, y - 1, k);
        } else if (c == 1) {
            int x, y, k;
            cin >> x >> y >> k;
            segTree.range_mul(x - 1, y - 1, k);
        } else if (c == 3) {
            int x, y;
            cin >> x >> y;
            cout << segTree.range_sum(x - 1, y - 1)  << '\n';
        }
    }
    return 0;
}