#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];


struct Node {
    int l, r;
    vector<int> v;
    vector<ll> s;
    bool operator<(const Node& w) {
        return r < w.r;
    }
};
int main() {
    const int mid = 316;
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n + 1; i++) scanf("%d", w + i);
    vector<Node> e;
    for (int i = 0; i * mid + 1 <= n; i++) {
        e.push_back({i * mid + 1, min(n, (i + 1) * mid), {}, {}});
        auto& u = e.back();
        for (int j = i * mid + 1; j <= min(n, (i + 1) * mid); j++) u.v.push_back(w[j]);
        sort(u.v.begin(), u.v.end());
        for (int j = 0; j < u.v.size(); j++) u.s.push_back(j ? u.s[j - 1] + u.v[j] : u.v[j]);
    }
    while (m--) {
        int op, l, r, a, b;
        scanf("%d", &op);
        if (op & 1) {
            scanf("%d%d", &a, &b);
            auto& u = *lower_bound(e.begin(), e.end(), Node{0, a, {}, {}});
            for (int i = 0; i < u.v.size(); i++)
                if (u.v[i] == w[a]) {
                    u.v[i] = w[a] = b;
                    break;
                }
            sort(u.v.begin(), u.v.end());
            for (int j = 0; j < u.v.size(); j++) u.s[j] = (j ? u.s[j - 1] + u.v[j] : u.v[j]);
        } else {
            scanf("%d%d%d%d", &l, &r, &a, &b);
            ll res = 0;
            auto u = lower_bound(e.begin(), e.end(), Node{0, l, {}, {}});
            while (u != e.end() && u->l <= r) {
                if (u->l >= l && u->r <= r) {
                    auto x = lower_bound(u->v.begin(), u->v.end(), a), y = upper_bound(u->v.begin(), u->v.end(), b);
                    res += (x - u->v.begin()) * (ll)a + (u->v.end() - y) * (ll)b;
                    if (y > x) res += u->s[y - u->v.begin() - 1] - (x != u->v.begin() ? u->s[x - u->v.begin() - 1] : 0);
                } else for (int i = max(l, u->l); i <= min(r, u->r); i++) res = res + max(a, min(b, w[i]));
                ++u;
            }
            printf("%lld\n", res);
        }
    }   
    return 0;
}