#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long LL;
typedef pair<int, LL> PIL;

const int N = 100010, V = 1000000000;

struct Node {
    int l, r, cnt;
    LL sum;
};

int n, q, a[N];

struct PSegTree {
    Node seg[N * 100];
    int rt[N], idx;
    void PushUp(int u) {
        seg[u].cnt = seg[seg[u].l].cnt + seg[seg[u].r].cnt;
        seg[u].sum = seg[seg[u].l].sum + seg[seg[u].r].sum;
    }
    void Insert(int u1, int &u2, int ul, int ur, int x) {
        u2 = ++idx;
        seg[u2] = seg[u1];
        if (ul == ur) {
            ++seg[u2].cnt;
            seg[u2].sum += x;
            return;
        }
        int mid = ul + ur >> 1;
        if (mid >= x) Insert(seg[u1].l, seg[u2].l, ul, mid, x);
        else Insert(seg[u1].r, seg[u2].r, mid + 1, ur, x);
        PushUp(u2);
    }
    PIL Query(int u1, int u2, int ul, int ur, int l, int r) {
        if (l <= ul && ur <= r) return { seg[u2].cnt - seg[u1].cnt, seg[u2].sum - seg[u1].sum };
        int mid = ul + ur >> 1;
        PIL ret = { 0, 0LL };
        if (mid >= l) {
            PIL res = Query(seg[u1].l, seg[u2].l, ul, mid, l, r);
            ret.first += res.first, ret.second += res.second;
        }
        if (mid + 1 <= r) {
            PIL res = Query(seg[u1].r, seg[u2].r, mid + 1, ur, l, r);
            ret.first += res.first, ret.second += res.second;
        }
        return ret;
    }
};
PSegTree pst;

int main() {
    // freopen("query.in", "r", stdin);
    // freopen("query.out", "w", stdout);

    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        pst.Insert(pst.rt[i - 1], pst.rt[i], 1, V, a[i]);
    }
    while (q--) {
        int op, l, r, x;
        scanf("%d%d%d%d", &op, &l, &r, &x);
        PIL p = pst.Query(pst.rt[l - 1], pst.rt[r], 1, V, x + 1, V);
        printf("%lld\n", p.second - 1LL * p.first * x);
    }

    return 0;
}