1
#include<bits/stdc++.h>
2
const int N = 1e5 + 10;
3
int n;
4
using namespace std;
5
#define int long long
6
int a[N];
7
const int mod = 571373;
8

9
namespace Segmenttree
10
{
11
  #define ls (u << 1)
12
  #define rs ((u << 1) | 1)
13
  int tree[N << 2];
14
  int tagcheng[N << 2], tagjia[N << 2];
15
  void init()
16
  {
17
    for(int i = 1;i < 4 * n;i++)
18
      tagcheng[i] = 1, tagjia[i] = 0;
19
  }
20
  void pushup(int u)
21
  {
22
    tree[u] = (tree[ls] + tree[rs]) % mod;
23
  }
24

25
  void build(int u, int l, int r)
26
  {
27
    if(l == r)
28
    {
29
      tree[u] = a[l];
30
      return;
31
    }
32
    int mid = (l + r) >> 1;
33
    build(ls, l, mid);
34
    build(rs, mid + 1, r);
35
    pushup(u);
36
  }
37

38
  void pushdown(int u, int l, int r)
39
  {
40
    int mid = (l + r) >> 1;
41
    //[l, mid]、[mid + 1, r]
42
    tree[ls] = (tree[ls] * tagcheng[u] + tagjia[u] * (mid - l + 1)) % mod;
43
    tree[rs] = (tree[rs] * tagcheng[u] + tagjia[u] * (r - mid)) % mod;
44
    tagcheng[ls] = tagcheng[ls] * tagcheng[u] % mod;
45
    tagcheng[rs] = tagcheng[rs] * tagcheng[u] % mod;
46
    tagjia[ls] = (tagjia[ls] * tagcheng[u] + tagjia[u]) % mod;
47
    tagjia[rs] = (tagjia[rs] * tagcheng[u] + tagjia[u]) % mod;
48
    tagjia[u] = 0;
49
    tagcheng[u] = 1;
50
  }
51

52
  void change(int u, int l, int r, int L, int R, int val, int type)
53
  {
54
    if(L <= l && r <= R)
55
    {
56
//      cout << l << " " << r << " was included"<<endl;
57
      if(type == 0)
58
      {
59
        tree[u] = (tree[u] + val * (r - l + 1)) % mod;
60
        tagjia[u] = (tagjia[u] + val) % mod;
61
      }
62
      else
63
      {
64

65
        tree[u] = tree[u] * val % mod;
66
        tagcheng[u] = tagcheng[u] * val % mod;
67
        tagjia[u] = tagjia[u] * val % mod;
68
//        if(l == 4 && r == 4) cout << u<<" "<< val << " " << type << "qaqaqaq"<< "  " << tree[u]  << " "<< endl;
69
      }
70
      return;
71
    }
72
//    cout << l << " " << r << endl;
73
    pushdown(u, l, r);
74
    int mid = (l + r) >> 1;
75
    if(L <= mid) change(ls, l, mid, L, R, val, type);
76
    if(R > mid) change(rs, mid + 1, r, L, R, val, type);
77
    pushup(u);
78
  }
79

80
  int query(int u, int l, int r, int L, int R)
81
  {
82
    if(L <= l && r <= R)
83
    {
84
//      cout << "query : " << l << " " << r << "sum: " << tree[u] << "    " << u << endl;
85
      return tree[u];
86
    }
87
    int ans = 0;
88
    pushdown(u, l, r);
89
    int mid = (l + r) >> 1;
90
    if(L > r || R < l) return 0;
91
    if(L <= mid) ans = (ans + query(ls, l, mid, L, R)) % mod;
92
    if(R > mid) ans = (ans + query(rs, mid + 1, r, L, R)) % mod;
93
//    cout << "query : " << l << " " << r << "sum: " << ans << "    " << u << endl;
94
    return ans;
95
  }
96
}
97
signed main()
98
{
99
//  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
100
  int q, m;
101
  cin >> n >> q >> m;
102
  for(int i = 1;i <= n;i++)
103
    cin >> a[i];
104
  int opt;
105
  Segmenttree::init();
106
  Segmenttree::build(1, 1, n);
107
  while(q--)
108
  {
109
    int x, y, k;
110
    cin >> opt;
111
    if(opt == 1)
112
    {
113
      cin >> x >> y >> k;
114
      Segmenttree::change(1, 1, n, x, y, k, 1);
115
//      cout << "qwq" << Segmenttree::query(1, 1, n, 4, 4) << '\n';
116
    }
117
    else if(opt == 2)
118
    {
119
      cin >> x >> y >> k;
120
      Segmenttree::change(1, 1, n, x, y, k, 0);
121
//      cout << "qwq" << " " << Segmenttree::query(1, 1, n, x, y) << '\n';
122
    }
123
    else
124
    {
125
      cin >> x >> y;
126
      cout << Segmenttree::query(1, 1, n, x, y) << '\n';
127
    }
128
  }
129
  return 0;
130
}