#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <random>
#include <ctime>
#include <chrono>
#include <numeric>
#include <iomanip>
#include <cassert>

typedef long long ll;
typedef double lf;
typedef unsigned long long ull;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 5e5 + 10, MAXB = 750, B = 720;

int n, q; ll a[MAXN];

int bel[MAXN], lb[MAXB], rb[MAXB];
bitset <MAXN> cnt[MAXB], avl;
ll sum[MAXB], add[MAXB]; int cov[MAXB];

inline void Set(int i) { sum[bel[i]] += a[i]; if (a[i] <= 5e5) cnt[bel[i]].set(a[i]); }
inline void Rebuild(int u)
{
    for (int i = lb[u]; i <= rb[u]; i++)
        if (a[i] <= 5e5) cnt[u].reset(a[i]);
    for (int i = lb[u]; i <= rb[u]; i++) a[i] = (~cov[u] ? cov[u] : a[i]) + add[u];
    sum[u] = add[u] = 0, cov[u] = -1;
}
inline void Aset(int x) { (x <= 5e5) && (avl.set(x), 0); }
inline void Areset(int x) { (x <= 5e5) && (avl.reset(x), 0); }
inline bool Test(int l, int r, int x)
{
    if (x > 5e5) return 0;
    if (avl.test(x)) return 1;
    for (int i = l; i <= r; i++)
        if (cov[i] == x) return 1;
        else if (cov[i] == -1 && x + add[i] <= 5e5 && cnt[i].test(x + add[i])) return 1;
    return 0;
}

int main()
{
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n), Read(q);
    for (int i = 1; i <= n; i++) Read(a[i]);

    for (int i = 1; i <= n; i++) bel[i] = (i - 1) / B + 1;
    for (int i = 1; i <= bel[n]; i++) lb[i] = (i - 1) * B + 1, rb[i] = min(n, i * B), cov[i] = -1;
    for (int i = 1; i <= n; i++) Set(i);

    int op, l, r, x;
    while (q--)
    {
        Read(op), Read(l), Read(r);
        if (op == 1)
        {
            Read(x);
            if (bel[l] == bel[r])
            {
                Rebuild(bel[l]);
                for (int i = l; i <= r; i++) a[i] = x;
                for (int i = lb[bel[l]]; i <= rb[bel[l]]; i++) Set(i);
                continue;
            }
            Rebuild(bel[l]), Rebuild(bel[r]);
            for (int i = l; bel[i] == bel[l]; i++) a[i] = x;
            for (int i = lb[bel[l]]; i <= rb[bel[l]]; i++) Set(i);
            for (int i = r; bel[i] == bel[r]; i--) a[i] = x;
            for (int i = lb[bel[r]]; i <= rb[bel[r]]; i++) Set(i);
            for (int i = bel[l] + 1; i < bel[r]; i++) add[i] = 0, cov[i] = x, sum[i] = (ll)B * x;
        }
        else if (op == 2)
        {
            if (bel[l] == bel[r])
            {
                Rebuild(bel[l]);
                for (int i = l; i <= r; i++) Aset(a[i]);
                int mex = 0; while (avl.test(mex)) mex++;
                for (int i = l; i <= r; i++) Areset(a[i]), a[i] += mex;
                for (int i = lb[bel[l]]; i <= rb[bel[l]]; i++) Set(i);
                continue;
            }
            Rebuild(bel[l]), Rebuild(bel[r]);
            for (int i = l; bel[i] == bel[l]; i++) Aset(a[i]);
            for (int i = r; bel[i] == bel[r]; i--) Aset(a[i]);
            int mex = 0; while (Test(bel[l] + 1, bel[r] - 1, mex)) mex++;
            for (int i = l; bel[i] == bel[l]; i++) Areset(a[i]), a[i] += mex;
            for (int i = r; bel[i] == bel[r]; i--) Areset(a[i]), a[i] += mex;
            for (int i = bel[l] + 1; i < bel[r]; i++) add[i] += mex, sum[i] += (ll)B * mex;
            for (int i = lb[bel[l]]; i <= rb[bel[l]]; i++) Set(i);
            for (int i = lb[bel[r]]; i <= rb[bel[r]]; i++) Set(i);
        }
        else
        {
            ll ans = 0;
            if (bel[l] == bel[r])
            {
                Rebuild(bel[l]);
                for (int i = l; i <= r; i++) ans += a[i];
                for (int i = lb[bel[l]]; i <= rb[bel[l]]; i++) Set(i);
                cout << ans << "\n";
                continue;
            }
            Rebuild(bel[l]), Rebuild(bel[r]);
            for (int i = l; bel[i] == bel[l]; i++) ans += a[i];
            for (int i = r; bel[i] == bel[r]; i--) ans += a[i];
            for (int i = bel[l] + 1; i < bel[r]; i++) ans += sum[i];
            for (int i = lb[bel[l]]; i <= rb[bel[l]]; i++) Set(i);
            for (int i = lb[bel[r]]; i <= rb[bel[r]]; i++) Set(i);
            cout << ans << "\n";
        }
    }
    return 0;
}