Problem: Sarah has always been a lover of nature, and a couple of years ago she saved up enough money to travel the world and explore all the things built by nature over its lifetime on earth. During this time she visited some truly special places which were left untouched for centuries, from watching icebergs in freezing weather to scuba-diving in oceans and admiring the sea life, residing unseen. These experiences were enhanced with breathtaking views built by mountains over time and left there for visitors to see for years on end. Over time, all these expeditions took a toll on Sarah and culminated in her decision to settle down in the suburbs and live a quiet life. 

However, as Sarah's love for nature never faded, she started growing flowers in her garden in an attempt to stay connected with nature. At the beginning she planted only blue orchids, but over time she started using different flower types to add variety to her collection of flowers. This collection of flowers can be represented as an array of N flowers and the i-th of them has a type associated with it, denoted as A_i. Each resident, passing by her collection and limited by the width of his view, can only see K contiguous flowers at each moment in time. To see the whole collection, the resident will look at the first K contiguous flowers A_1, A_2, ..., A_K, then shift his view by one flower and look at the next section of K contiguous flowers A_2, A_3, ..., A_{K+1} and so on until they scan the whole collection, ending with section A_{N-K+1}, ..., A_{N-1}, A_N.

Each resident determines the beautiness of a section of K flowers as the number of distinct flower types in that section. Furthermore, the beautiness of the whole collection is calculated by summing the beautiness values of each contiguous section. Formally, beautiness B_i of a section starting at the i-th position is calculated as B_i = distinct(A_i, A_{i+1}, ..., A_{i+K-1}), and beautiness of the collection B is calculated as B=B_1 + B_2 + ... + B_{N-K+1}.

In addition, as Sarah wants to keep her collection of flowers have a fresh feel, she can also pick two points L and R, dispose flowers between those two points and plant new flowers, all of them being the same type.

You will be given Q queries and each of those queries will be of the following two types: 

  1. You will be given three integers L, R, X describing that Sarah has planted flowers of type X between positions L and R inclusive. Formally collection is changed such that A[i]=X for all i in range [L.. R]. 
  2. You will be given integer K, width of the resident's view and you have to determine the beautiness value B resident has associated with the collection 



For each query of second type print the result – beautiness B of the collection.

Input

First line contains two integers N and Q \;(1 ≤ N, Q ≤ 10^5)  — number of flowers and the number of queries, respectively.

The second line contains N integers A_1, A_2, ..., A_N\;(1 ≤ A_i ≤ 10^9)  — where A_i represents type of the i-th flower.

Each of the next Q lines describe queries and start with integer T∈\{1, 2\}. 

  * If T = 1, there will be three more integers in the line L, R, X\;(1 ≤ L, R ≤ N;\; 1 ≤ X ≤ 10^9)  — L and R describing boundaries and X describing the flower type 
  * If T = 2, there will be one more integer in the line K\;(1 ≤ K ≤ N)  — resident's width of view 

Output

For each query of the second type print the beautiness B of the collection.

Example

Input


5 5
1 2 3 4 5
2 3
1 1 2 5
2 4
1 2 4 5
2 2


Output


9
6
4

Note

Let's look at the example.

Initially the collection is [1, 2, 3, 4, 5]. In the first query K = 3, we consider sections of three flowers with the first being [1, 2, 3]. Since beautiness of the section is the number of distinct flower types in that section, B_1 = 3. Second section is [2, 3, 4] and B_2 = 3. Third section is [3, 4, 5] and B_3 = 3, since the flower types are all distinct. The beautiness value resident has associated with the collection is B = B_1 + B_2 + B_3 = 3 + 3 + 3 = 9.

After the second query, the collection becomes [5, 5, 3, 4, 5]. 

For the third query K = 4, so we consider sections of four flowers with the first being [5, 5, 3, 4]. There are three distinct flower types [5, 3, 4] in this section, so B_1 = 3. Second section [5, 3, 4, 5] also has 3 distinct flower types, so B_2 = 3. The beautiness value resident has associated with the collection is B = B_1 + B_2 = 3 + 3 = 6

After the fourth query, the collection becomes [5, 5, 5, 5, 5].

For the fifth query K = 2 and in this case all the four sections are same with each of them being [5, 5]. Beautiness of [5, 5] is 1 since there is only one distinct element in this section [5]. Beautiness of the whole collection is B = B_1 + B_2 + B_3 + B_4 = 1 + 1 + 1 + 1 = 4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 5;
long long read() {
  long long s = 0;
  char c = getchar(), lc = '+';
  while (c < '0' || '9' < c) lc = c, c = getchar();
  while ('0' <= c && c <= '9') s = s * 10 + c - '0', c = getchar();
  return lc == '-' ? -s : s;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + '0');
  else
    write(x / 10), putchar(x % 10 + '0');
}
void print(long long x, char c = '\n') {
  write(x);
  putchar(c);
}
struct segment_tree {
  long long tot[N * 4], sum[N * 4], tag[N * 4];
  void update(long long w, long long l, long long r, long long y) {
    tag[w] += y;
    tot[w] += y * (r - l + 1);
    sum[w] += (l + r) * (r - l + 1) / 2 * y;
  }
  void push_up(long long w) {
    tot[w] = tot[(w * 2)] + tot[(w * 2 + 1)];
    sum[w] = sum[(w * 2)] + sum[(w * 2 + 1)];
  }
  void push_down(long long w, long long l, long long r) {
    if (!tag[w]) return;
    update((w * 2), l, ((l + r) / 2), tag[w]);
    update((w * 2 + 1), ((l + r) / 2) + 1, r, tag[w]);
    tag[w] = 0;
  }
  void add(long long w, long long l, long long r, long long ql, long long qr,
           long long y) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) return update(w, l, r, y);
    push_down(w, l, r);
    if (ql <= ((l + r) / 2)) add((w * 2), l, ((l + r) / 2), ql, qr, y);
    if (qr > ((l + r) / 2)) add((w * 2 + 1), ((l + r) / 2) + 1, r, ql, qr, y);
    push_up(w);
  }
  void add(long long w, long long l, long long r, long long x, long long y) {
    add(w, l, r, x, x, y);
  }
  long long querytot(long long w, long long l, long long r, long long ql,
                     long long qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return tot[w];
    push_down(w, l, r);
    return querytot((w * 2), l, ((l + r) / 2), ql, qr) +
           querytot((w * 2 + 1), ((l + r) / 2) + 1, r, ql, qr);
  }
  long long querysum(long long w, long long l, long long r, long long ql,
                     long long qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[w];
    push_down(w, l, r);
    return querysum((w * 2), l, ((l + r) / 2), ql, qr) +
           querysum((w * 2 + 1), ((l + r) / 2) + 1, r, ql, qr);
  }
} t, tl, tr;
struct Query {
  long long opt, l, r, x;
} q[N];
struct node {
  long long l, r, x;
  bool operator<(const node &a) const { return l == a.l ? r < a.r : l < a.l; }
};
set<node> s, c[N];
long long a[N], b[N], last[N];
signed main() {
  long long n = read(), m = read(), cnt = n;
  for (long long i = 1; i <= n; i++) b[i] = a[i] = read();
  for (long long i = 1; i <= m; i++) {
    q[i].opt = read();
    if (q[i].opt == 1)
      q[i].l = read(), q[i].r = read(), b[++cnt] = q[i].x = read();
    else
      q[i].x = read();
  }
  sort(b + 1, b + 1 + cnt);
  cnt = unique(b + 1, b + 1 + cnt) - b - 1;
  for (long long i = 1; i <= n; i++)
    a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
  for (long long i = 1; i <= m; i++)
    if (q[i].opt == 1) q[i].x = lower_bound(b + 1, b + 1 + cnt, q[i].x) - b;
  for (long long i = 1; i <= n; i++) s.insert((node){i, i, a[i]});
  for (long long i = 1; i <= n; i++) c[a[i]].insert((node){i, i, a[i]});
  for (long long i = 1; i <= n; i++) {
    t.add(1, 1, n, i - last[a[i]], 1);
    tl.add(1, 1, n, last[a[i]], 1);
    tr.add(1, 1, n, i, 1);
    last[a[i]] = i;
  }
  for (long long i = 1; i <= cnt; i++) c[i].insert((node){0, 0, i});
  for (long long i = 1; i <= m; i++)
    if (q[i].opt == 1) {
      long long l = q[i].l, r = q[i].r, x = q[i].x;
      auto tmp = s.upper_bound((node){l, n, 0});
      tmp--;
      if ((tmp->l) != l) {
        c[tmp->x].insert((node){tmp->l, l - 1, tmp->x});
        c[tmp->x].insert((node){l, tmp->r, tmp->x});
        c[tmp->x].erase(*tmp);
        s.insert((node){tmp->l, l - 1, tmp->x});
        s.insert((node){l, tmp->r, tmp->x});
        s.erase(tmp);
      }
      tmp = s.upper_bound((node){r, n, 0});
      tmp--;
      if ((tmp->r) != r) {
        c[tmp->x].insert((node){tmp->l, r, tmp->x});
        c[tmp->x].insert((node){r + 1, tmp->r, tmp->x});
        c[tmp->x].erase(*tmp);
        s.insert((node){tmp->l, r, tmp->x});
        s.insert((node){r + 1, tmp->r, tmp->x});
        s.erase(tmp);
      }
      auto now = s.lower_bound((node){l, 0, 0});
      while (now != s.end() && (now->r) <= r) {
        auto nxt = now;
        nxt++;
        auto M = c[now->x].lower_bound(*now), L = M, R = M;
        L--, R++;
        t.add(1, 1, n, 1, (M->l) - (M->r));
        tl.add(1, 1, n, (M->l), (M->r) - 1, -1);
        tr.add(1, 1, n, (M->l) + 1, M->r, -1);
        t.add(1, 1, n, (M->l) - (L->r), -1);
        tl.add(1, 1, n, L->r, -1);
        tr.add(1, 1, n, M->l, -1);
        if (R != c[now->x].end()) {
          t.add(1, 1, n, (R->l) - (M->r), -1);
          tl.add(1, 1, n, M->r, -1);
          tr.add(1, 1, n, R->l, -1);
          t.add(1, 1, n, (R->l) - (L->r), 1);
          tl.add(1, 1, n, L->r, 1);
          tr.add(1, 1, n, R->l, 1);
        }
        c[now->x].erase(M);
        s.erase(now);
        now = nxt;
      }
      c[x].insert((node){l, r, x});
      s.insert((node){l, r, x});
      auto M = c[x].lower_bound((node){l, r, x}), L = M, R = M;
      L--, R++;
      t.add(1, 1, n, 1, (M->r) - (M->l));
      tl.add(1, 1, n, (M->l), (M->r) - 1, 1);
      tr.add(1, 1, n, (M->l) + 1, M->r, 1);
      t.add(1, 1, n, (M->l) - (L->r), 1);
      tl.add(1, 1, n, L->r, 1);
      tr.add(1, 1, n, M->l, 1);
      if (R != c[x].end()) {
        t.add(1, 1, n, (R->l) - (M->r), 1);
        tl.add(1, 1, n, M->r, 1);
        tr.add(1, 1, n, R->l, 1);
        t.add(1, 1, n, (R->l) - (L->r), -1);
        tl.add(1, 1, n, L->r, -1);
        tr.add(1, 1, n, R->l, -1);
      }
    } else
      print(t.querysum(1, 1, n, 1, q[i].x) +
            t.querytot(1, 1, n, q[i].x + 1, n) * q[i].x -
            (tr.querysum(1, 1, n, n - q[i].x + 1, n) -
             tr.querytot(1, 1, n, n - q[i].x + 1, n) * (n - q[i].x + 1)) +
            (tl.querysum(1, 1, n, n - q[i].x + 1, n) -
             tl.querytot(1, 1, n, n - q[i].x + 1, n) * (n - q[i].x + 1)));
  return 0;
}