#include <bits/stdc++.h>
#define ll long long
#define eb push_back
namespace IO {
	const int S = (1 << 21);
	int digital = 2;
	bool is_round = 1;
	char b[S], *m = b, *n = b, g[S], *p = g;
	inline void f() { fwrite(g, 1, p - g, stdout), p = g; }
	struct R {
		inline bool w(char c) { return 47 < c && c < 58; }
		inline bool y(char c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t'; }
		inline char i() { if (m == n) n = (m = b) + fread(b, 1, S, stdin); return m == n ? ' ' : *m++; }
		template <class T> inline R &operator>>(T &x) { char c = i(); T f = 1; for (x = 0; !w(c);) { if(c == '-') f = -1; c = i(); } while (w(c)) x *= 10, x += c ^ 48, c = i(); x *= f; return *this; }
		inline R &operator>>(char *s) { int l = 0; char c; operator>>(c); for (; !y(c); s[l++] = c, c = i()) ; s[l] = '\0'; return *this; }
		inline R &operator>>(char &c) { do c = i(); while (y(c)); return *this; }
		template<class T> void tie(T x) {}
	} cin;
#define endl '\n'
	struct W {
		inline void o(char c) { *p++ = c; if (p - g == S) f(); }
		template <class T> inline W &operator<<(T x) { if (!x) return o(48), *this; if(x < 0) o('-'), x = -x; static int s[64], t = 0; while (x) s[++t] = x % 10, x /= 10; while (t) o(s[t--] + 48); return *this; }
		inline W &operator<<(char c) { o(c); return *this; }
		template <class T> inline W &operator<<(T *s) { int c = 0; while (s[c]) o(s[c++]); return *this; }
		template<class T> void tie(T x) {}
		~W() { f(); }
	} cout;
	struct E { template <class T> E &operator<<(T x) { return *this; } } cerr;
} ;

#define cin IO::cin
#define cout IO::cout
using namespace std;
const int N = 200200, B = 505, TEST = 0, OPT = 0, DBG = 0;
int n, m, s, t, sz;
int a[N];
int bl[B], br[B], fm[N];
int cnt[N][B];
int fz[N];
bool vis[N];
ll sum[B], f[B][B], tagx[B][B], tagy[B][B];
struct node{
    int l, r, col;
    node() {}
    node(int _l, int _r, int _col)
        : l(_l), r(_r), col(_col) {}
} cc;
vector<node> c[B];
inline void getinc(int t) {
    c[t].clear();
    for (int x = bl[t], y; x <= br[t]; x = y + 1) {
        y = x;
        while (y < br[t] && a[y + 1] == a[y]) ++y;
        c[t].eb(node(x, y, a[x]));
    }
    return;
}
inline void bckinc(int t) {
    sz = c[t].size();
    for (int i = 0; i < sz; ++i) {
        cc = c[t][i];
        fill(a + cc.l, a + cc.r + 1, cc.col);
    }
    return;
}
inline long long sqr(int x) {return 1ll * x * x;}
inline int qr(int x, int v) {return cnt[v][x] - cnt[v][x - 1];}
void init() {
    s = min(n, 1400);
    for (int l = 1, r = s; l <= n; l = r + 1, r = min(r + s, n)) {
        bl[++t] = l, br[t] = r;
        for (int i = l; i <= r; ++i) fm[i] = t;
        getinc(t);
        if (c[t].size() > 1) for (int i = l; i <= r; ++i) ++cnt[a[i]][t];
        for (int i = 1; i <= n; ++i) cnt[i][t] += cnt[i][t - 1], sum[t] += sqr(cnt[i][t]);
    }
    for (int i = 1; i <= t; ++i) {
        for (int j = 1; j <= n; ++j) f[i][i] += sqr(cnt[j][i]);
        for (int j = i + 1; j <= t; ++j) {
            f[i][j] = f[i][j - 1];
            sz = c[j].size();
            for (int k = 0; k < sz; ++k) {
                cc = c[j][k];
                if (!vis[cc.col]) f[i][j] += 1ll * cnt[cc.col][i] * qr(j, cc.col), vis[cc.col] = 1;
            }
            for (int k = 0; k < sz; ++k) vis[c[j][k].col] = 0;
        }
    }
    return;
}
vector<int> vec;
inline void add(int k, int v, ll x) {
    if (x == 0) return;
    for (int i = 1; i < k; ++i) tagx[k][i] += x * cnt[v][i];
    for (int i = k; i <= t; ++i) {
        ll v1 = x * cnt[v][i], v2 = v1 + sqr(x);
        tagx[i][i] += v1, tagy[k][i] += v2, sum[i] += sqr(x) + (v1 << 1), cnt[v][i] += x;
    }
    return;
}
inline ll askf(int l, int r) {
    ll res = f[l][r];
    for (int i = 1; i <= r; ++i) res += tagx[i][l];
    for (int i = 1; i <= l; ++i) res += tagy[i][r];
    return res;
}
inline ll ask(int l, int r) {
    if (l > r) return 0;
    return sum[r] + sum[l - 1] - askf(l - 1, r) * 2;
}
void updsm(int id, int l, int r, int v) {
    if (c[id].size() == 1 && (v == c[id][0].col || l == bl[id] && r == br[id])) return c[id][0].col = v, void();
    bckinc(id);
    bool flg = 1;
    for (int i = bl[id]; i <= br[id]; ++i) if (i < l || i > r) flg &= (a[i] == v);
    if (flg) {
        sz = c[id].size();
        for (int i = 0; i < sz; ++i) {
            cc = c[id][i];
            add(id, cc.col, -(cc.r - cc.l + 1));
        }
    }
    else {
        fz[v] += (!flg) * (r - l + 1), vec.eb(v), vis[v] = 1;
        if (c[id].size() != 1) for (int i = l; i <= r; ++i) {
            fz[a[i]]--;
            if (!vis[a[i]]) vec.eb(a[i]), vis[a[i]] = 1;
        }
        else for (int i = bl[id]; i <= br[id]; ++i) if (i < l || i > r) {
            ++fz[a[i]];
            if (!vis[a[i]]) vec.eb(a[i]), vis[a[i]] = 1;
        }
        sz = vec.size();
        for (int k = 0; k < sz; ++k) {
            int x = vec[k];
            add(id, x, fz[x]), fz[x] = vis[x] = 0; vec.clear();
        }
    }
    for (int i = l; i <= r; ++i) a[i] = v;
    getinc(id);
    return;
}
void updlrg(int id, int x) {
    if (c[id].size() == 1) c[id][0].col = x;
    else {
        sz = c[id].size();
        for (int i = 0; i < sz; ++i) cc = c[id][i], add(id, cc.col, -(cc.r - cc.l + 1));
        c[id].clear(), c[id].eb(node(bl[id], br[id], x));
    }
    return;
}
void change(int l, int r, int x) {
    int il = fm[l], ir = fm[r];
    if (il == ir) return updsm(il, l, r, x), void();
    updsm(il, l, br[il], x), updsm(ir, bl[ir], r, x);
    for (int i = il + 1; i < ir; ++i) updlrg(i, x);
    return;
}
ll query(int l, int r) {
    int il = fm[l], ir = fm[r];
    ll sum = 0;
    if (il == ir) {
        bckinc(il);
        for (int i = l; i <= r; ++i) ++fz[a[i]];
        for (int i = l; i <= r; ++i) if (!vis[a[i]]) sum += sqr(fz[a[i]]), vis[a[i]] = 1;
        for (int i = l; i <= r; ++i) vis[a[i]] = 0, fz[a[i]] = 0;
        return sum;
    }
    bckinc(il), bckinc(ir);
    for (int i = l; i <= br[il]; ++i) {
        ++fz[a[i]];
        if (!vis[a[i]]) vec.eb(a[i]), vis[a[i]] = 1;
    }
    for (int i = bl[ir]; i <= r; ++i) {
        ++fz[a[i]];
        if (!vis[a[i]]) vec.eb(a[i]), vis[a[i]] = 1;
    }
    for (int i = il + 1, pc; i < ir; ++i) if (c[i].size() == 1) {
        fz[(pc = c[i][0].col)] += br[i] - bl[i] + 1;
        if (!vis[pc]) vec.eb(pc), vis[pc] = 1;
    }
    sum = ask(il + 1, ir - 1), sz = vec.size();
    for (int i = 0; i < sz; ++i) {
        int x = vec[i];
        sum += sqr(fz[x]) + 2ll * (cnt[x][ir - 1] - cnt[x][il]) * fz[x];
        vis[x] = 0, fz[x] = 0;
    }
    vec.clear();
    return sum;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    init();
    ll lstans = 0;
    for (ll i = 1, op, l, r, x; i <= m; ++i) {
        cin >> op >> l >> r;
        if (!TEST) lstans %= (1ll << 32), l ^= lstans, r ^= lstans;
        if (op == 1) {
            cin >> x, x ^= TEST ? 0 : lstans;
            change(l, r, x);
        }
        else cout << (lstans = (query(l, r) - r + l - 1) / 2) << '\n';
    }
    return 0;
}