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;
constexpr int Maxn = 2e5 + 5;
int n, q;
int a[Maxn];
template <typename _Tp>
class range {
 public:
 public:
  range() : l(0), r(0), v(_Tp()) {}
  range(int l, int r, const _Tp &v) : l(l), r(r), v(v) {}
  range(const range &x) : l(x.l), r(x.r), v(x.v) {}
  friend bool operator<(const range &x, const range &y) { return x.l < y.l; }
  inline int left(void) const { return l; }
  inline int right(void) const { return r; }
  inline _Tp value(void) const { return v; }

 private:
  int l, r;
  mutable _Tp v;
};
template <typename _Tp>
class range_tree {
 public:
  typedef
      typename set<range<_Tp>>::const_reverse_iterator const_reverse_iterator;

 private:
  void insert_to(const range<_Tp> &_r);
  void erase_from(const range<_Tp> &_r);

 public:
  range_tree() : T() {}
  range_tree(const range_tree &x) : T(x.T) {}
  void insert(const range<_Tp> &_r) {
    T.insert(_r);
    insert_to(_r);
  }
  void erase(const range<_Tp> &_r) {
    T.erase(_r);
    erase_from(_r);
  }
  typename set<range<_Tp>>::iterator split(int p) {
    auto x = prev(T.upper_bound(range<_Tp>(p, -1, _Tp())));
    if (x->left() == p)
      return x;
    else if (p > x->right())
      return T.end();
    else {
      range<_Tp> t = *x;
      erase(t);
      insert(range<_Tp>(t.left(), p - 1, t.value()));
      insert(range<_Tp>(p, t.right(), t.value()));
      return T.find(range<_Tp>(p, t.right(), t.value()));
    }
  }
  std::pair<typename set<range<_Tp>>::iterator,
            typename set<range<_Tp>>::iterator>
  split_range(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    return {itl, itr};
  }
  void assign(int l, int r, _Tp v) {
    typename set<range<_Tp>>::iterator itl, itr;
    tie(itl, itr) = split_range(l, r);
    for (typename set<range<_Tp>>::iterator p = itl; p != itr; ++p)
      erase_from(*p);
    T.erase(itl, itr);
    insert(range<_Tp>(l, r, v));
  }

 private:
  std::set<range<_Tp>> T;
};
template <typename _Tp>
class fenwick_tree {
 public:
 private:
  int N;
  std::vector<_Tp> X, Y;
  inline void _M_check(int idx) {
    if (__builtin_expect(idx >= N || idx < 0, false)) {
      throw std::out_of_range("<Fenwick-tree::add> range error");
    }
  }
  inline void _M_check(int l, int r) {
    if (__builtin_expect(l > r || r >= N || l < 0, false)) {
      throw std::out_of_range("<Fenwick-tree::add> range error");
    }
  }
  void _M_add(std::vector<_Tp> &b, int idx, _Tp delta) {
    for (; idx < N; idx = idx | (idx + 1)) b[idx] = b[idx] + delta;
  }
  _Tp _M_sum(std::vector<_Tp> &b, int idx) {
    _Tp ret = 0;
    for (; idx >= 0; idx = (idx & (idx + 1)) - 1) ret = ret + b[idx];
    return ret;
  }

 public:
  fenwick_tree() { clear(); }
  fenwick_tree(int N) { resize(N, 0); }
  fenwick_tree(const fenwick_tree &arr) : N(arr.N), X(arr.X), Y(arr.Y) {}
  fenwick_tree(fenwick_tree &&arr) {
    N = arr.N, arr.N = 0;
    X.swap(arr.X), arr.X.clear();
    Y.swap(arr.Y), arr.Y.clear();
  }
  fenwick_tree(const std::vector<_Tp> &arr) { resize(arr); }
  inline void clear() { resize(0); }
  void resize(int len, _Tp val = _Tp(0)) {
    N = len;
    X.resize(N, _Tp(0));
    Y.resize(N, _Tp(0));
    if (val != _Tp(0)) add(0, N - 1, val);
  }
  void resize(const std::vector<_Tp> &arr) {
    N = (int)arr.size();
    X.resize(N, _Tp(0));
    Y.resize(N, _Tp(0));
    for (int i = 0; i < (int)arr.size(); ++i) add(i, i, arr[i]);
  }
  void add(int l, int r, _Tp val) {
    _M_check(l, r);
    _M_add(X, l, val);
    _M_add(Y, l, val * static_cast<_Tp>(l));
    if (r != N - 1) {
      _M_add(X, r + 1, -val);
      _M_add(Y, r + 1, -val * static_cast<_Tp>(r + 1));
    }
  }
  inline _Tp prefix_sum(int idx) {
    _M_check(idx);
    return _M_sum(X, idx) * static_cast<_Tp>(idx + 1) - _M_sum(Y, idx);
  }
  inline _Tp sum(int l, int r) {
    _M_check(l, r);
    _Tp _ans = prefix_sum(r);
    if (l != 0) _ans = _ans - prefix_sum(l - 1);
    return _ans;
  }
};
fenwick_tree<int64_t> f1(Maxn), f2(Maxn);
inline void modify(int k, int64_t v) {
  f1.add(k, n, -k * v);
  f2.add(k, n, v);
}
inline int64_t query(int k) { return f1.sum(k, k) + f2.sum(k, k) * k; }
set<range<int>> st[Maxn];
template <>
void range_tree<int>::insert_to(const range<int> &x) {
  int l = x.left(), r = x.right(), c = x.value();
  if (!st[c].empty()) {
    modify(st[c].begin()->left(), -1);
    modify(n - st[c].rbegin()->right() + 1, -1);
  }
  st[c].insert(x);
  modify(st[c].begin()->left(), 1);
  modify(n - st[c].rbegin()->right() + 1, 1);
  if (l != r) modify(1, r - l);
  auto it = st[c].find(x);
  if (it != st[c].begin()) modify(l - prev(it)->right(), 1);
  if (next(it) != st[c].end()) modify(next(it)->left() - r, 1);
  if (it != st[c].begin() && next(it) != st[c].end())
    modify(next(it)->left() - prev(it)->right(), -1);
}
template <>
void range_tree<int>::erase_from(const range<int> &x) {
  int l = x.left(), r = x.right(), c = x.value();
  if (l != r) modify(1, -(r - l));
  auto it = st[c].find(x);
  if (it != st[c].begin()) modify(l - prev(it)->right(), -1);
  if (next(it) != st[c].end()) modify(next(it)->left() - r, -1);
  if (it != st[c].begin() && next(it) != st[c].end())
    modify(next(it)->left() - prev(it)->right(), 1);
  modify(n - st[c].rbegin()->right() + 1, -1);
  modify(st[c].begin()->left(), -1);
  st[c].erase(x);
  if (!st[c].empty()) {
    modify(st[c].begin()->left(), 1);
    modify(n - st[c].rbegin()->right() + 1, 1);
  }
}
int64_t calc(int k) {
  int64_t ans = 1LL * k * n;
  ans -= query(k);
  return ans;
}
std::int32_t main(int argc, const char *argv[]) {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cout << std::fixed << std::setprecision(12);
  std::cerr << std::boolalpha;
  auto get_id = [&](int x) -> int {
    static std::unordered_map<int, int> mp;
    if (mp.find(x) == mp.end()) mp[x] = (int)mp.size() + 1;
    return mp[x];
  };
  cin >> n >> q;
  range_tree<int> T;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    a[i] = get_id(a[i]);
    T.insert(range<int>(i, i, a[i]));
  }
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      x = get_id(x);
      T.assign(l, r, x);
    } else {
      int x;
      cin >> x;
      cout << calc(x) << endl;
    }
  }
  std::exit(EXIT_SUCCESS);
}