#include <bits/stdc++.h>

constexpr int T(512), N(1e5 + 5), S(N / T + 1);
struct Qry {
  int l, r, id;
  bool operator<(const Qry &rhs) const {
    return l / T == rhs.l / T ? l / T & 1 ? r < rhs.r : r > rhs.r : l < rhs.l;
  }
};
int n, m;

int a[N], s[S];
void clear() {
  memset(a, 0, sizeof a);
  memset(s, 0, sizeof s);
}
void add(int p) {
  int t = p / T;
  for (int i = t * T; i <= p; i++) a[i]++;
  for (int i = 0; i < t; i++) s[i]++;
}
int ask(int p) {
  p = std::max(p, 0);
  return a[p] + s[p / T];
}


int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  std::cin >> n >> m;
  std::vector<int> a(n);
  for (int &x : a) std::cin >> x;
  auto b = a;
  std::sort(b.begin(), b.end());
  b.resize(std::unique(b.begin(), b.end()) - b.begin());
  for (int &x : a) x = std::lower_bound(b.begin(), b.end(), x) - b.begin();
  std::vector<long long> c(n + 1), d(n + 1);
  
  for (int i = 0; i < n; i++) {
    add(a[i]);
    c[i + 1] = c[i] + ask(a[i + 1] + 1);
    d[i + 1] = d[i] + i + 1 - ask(a[i]);
  }
  std::vector<Qry> q(m);
  for (int i = 0; i < m; i++) {
    std::cin >> q[i].l >> q[i].r;
    q[i].l--, q[i].r--;
    q[i].id = i;
  }
  std::sort(q.begin(), q.end());
  std::vector<long long> ans(m), out(m);
  std::vector<std::vector<std::array<int, 3>>> g(n), h(n);
  for (int i = 0, x = 1, y = 0; i < m; i++) {
    if (y != q[i].r) {
      ans[i] += c[q[i].r] - c[y];
      if (x) y < q[i].r ? g[x - 1].push_back({y + 1, q[i].r, -i - 1}) : g[x - 1].push_back({q[i].r + 1, y, i});
      y = q[i].r;
    }
    if (x != q[i].l) {
      ans[i] += d[q[i].l] - d[x];
      x < q[i].l ? h[y].push_back({x, q[i].l - 1, -i - 1}) : h[y].push_back({q[i].l, x - 1, i});
      x = q[i].l;
    }
  }
  clear();
  for (int i = 0; i < n; i++) {
    add(a[i]);
    for (auto [l, r, id] : g[i]) {
      int c = id < 0 ? id = -id - 1, -1 : 1;
      for (int j = l; j <= r; j++) {
    ans[id] += c * ask(a[j] + 1);
      }
    }
    for (auto [l, r, id] : h[i]) {
      int c = id < 0 ? id = -id - 1, -1 : 1;
      for (int j = l; j <= r; j++) {
    ans[id] += c * (i + 1 - ask(a[j]));
      }
    }
  }
  for (int i = 1; i < m; i++) ans[i] += ans[i - 1];
  for (int i = 0; i < m; i++) out[q[i].id] = ans[i];
  for (auto x : out) std::cout << x << "\n";
  return 0;
}

// Author:  HolyK
// Created: Tue Sep 14 14:01:15 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
inline char gc() {
  static constexpr int BufferSize = 1 << 22 | 5;
  static char buf[BufferSize], *p, *q;
  static std::streambuf *i = std::cin.rdbuf();
  return p == q ? p = buf, q = p + i->sgetn(p, BufferSize), p == q ? EOF : *p++ : *p++;
}
struct Reader {
  template <class T>
  Reader &operator>>(T &w) {
    char c, p = 0;
    for (; !std::isdigit(c = gc());) if (c == '-') p = 1;
    for (w = c & 15; std::isdigit(c = gc()); w = w * 10 + (c & 15)) ;
    if (p) w = -w;
    return *this;
  }
} cin;

constexpr int N(1e5 + 5), T(512);
LL cal(PII *a, PII *b, int l1, int r1, PII *c, PII *d, int l2, int r2) {
  LL res = 0;
  for (int now = 0; a < b; a++) {
    if (a->second < l1 || a->second >= r1) continue;
    for (; c < d && *c < *a; c++) {
      if (c->second < l2 || c->second >= r2) continue;
      now++;
    }
    res += now;
  }
  return res;
}

int n, m, a[N];
PII b[N], bb[N];
int c[N];
void add(int p, int x) {
  for (; p <= n; p += p & -p) c[p] += x;
}
int ask(int p) {
  int r = 0;
  for (; p; p -= p & -p) r += c[p];
  return r;
}
constexpr int S((N - 1 + T) / T);
LL pre[N], suf[N], cnt[S][N];

int main() {
  // freopen("t.in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cin >> n >> m;

  for (int i = 0; i < n; i++) {
    cin >> a[i];
    bb[i] = b[i] = {a[i], i};
  }
  std::sort(bb, bb + n);
  for (int l = 0, o = 0; l < n; l += T, o++) {
    int r = std::min(n, l + T);
    std::sort(b + l, b + r);
    
    for (int i = 0, j = l; i < n || j < r;) {
      if (j == r || i < n && bb[i] < b[j]) {
        cnt[o][bb[i].second] += j - l;
        i++;
      } else {
        j++;
      }
    }
    for (int i = 1; i < n; i++) cnt[o][i] += cnt[o][i - 1];
    
    for (int i = l; i < r; i++) {
      pre[i] = i - l - ask(a[i]);
      add(a[i], 1);
    }
    for (int i = l; i < r; i++) {
      add(a[i], -1);      
    }
    for (int i = r - 1; i >= l; i--) {
      suf[i] = ask(a[i]);
      add(a[i], 1);
    }
    for (int i = l; i < r; i++) {
      add(a[i], -1);
    }
    
    for (int i = l + 1; i < r; i++) pre[i] += pre[i - 1];
    for (int i = r - 2; i >= l; i--) suf[i] += suf[i + 1];
  }
  LL ans = 0;
  while (m--) {
    LL l, r;
    cin >> l >> r;
    l ^= ans, r ^= ans;
    l--, r--;
    int bl = l / T, br = r / T;
    if (bl == br) {
      ans = pre[r] - (l == bl * T ? 0 : pre[l - 1]);
      int x = bl * T, y = std::min(n, x + T);
      ans -= cal(b + x, b + y, x, l, b + x, b + y, l, r + 1);
    } else {
      ans = suf[l] + pre[r];
      ans += std::max(0, (br - bl - 1) * T) * (r - br * T + 1LL);
      
      for (int i = bl + 1; i < br; i++) {
        ans += suf[i * T];
        ans += cnt[i][i * T - 1];
        if (l) ans -= cnt[i][l - 1];
        ans -= cnt[i][r] - cnt[i][br * T - 1];
      }
      // std::cerr << ans << "\n";
      ans += cal(b + bl * T, b + bl * T + T, l, bl * T + T,
                 b + br * T, b + std::min(n, br * T + T), br * T, r + 1);
    }
    std::cout << ans << "\n";
    // break;
  }
  
  return 0;
}

// Author:  HolyK
// Created: Tue Sep 14 17:41:10 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(5e5 + 5), T(512), S((N - 1 + T) / T);
int n, m, a[N], b[N], c[N], pos[N], cnt[S][S];
struct LazyVector {
  std::vector<int> a, b;
  int c;
  LazyVector(int n) : a(n), b(n), c(0) {}
  void clear() { c++; }
  int &operator[](const int &i) {
    if (b[i] != c) b[i] = c, a[i] = 0;
    return a[i];
  }
};
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> m;
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    b[i] = a[i];
  }
  std::sort(b, b + n);
  int t = std::unique(b, b + n) - b;
  for (int i = 0; i < n; i++) {
    a[i] = std::lower_bound(b, b + t, a[i]) - b;
    c[a[i]]++;
  }
  for (int i = 1; i < t; i++) c[i] += c[i - 1];
  for (int i = n - 1; i >= 0; i--) {
    b[--c[a[i]]] = i;
    pos[i] = c[a[i]];
  }
  LazyVector v(t);
  for (int i = 0; i < n; i += T) {  
    int max = 0;
    v.clear();
    for (int j = i + T; j < n; j += T) {
      for (int k = j - T; k < j; k++) 
        smax(max, ++v[a[k]]);
      cnt[i / T][j / T] = max;
    }
  }
  int ans = 0;
  while (m--) {
    int l, r;
    std::cin >> l >> r;
    l ^= ans, r ^= ans;
    l--, r--;
    int bl = l / T, br = r / T;
    if (bl == br) {
      ans = 0;
      v.clear();
      for (int i = l; i <= r; i++) {
        smax(ans, ++v[a[i]]);
      }
    } else {
      ans = cnt[bl + 1][br];
      int y = bl * T + T, x = br * T;
      for (int i = l; i < y; i++) {
        while (pos[i] + ans < n && b[pos[i] + ans] <= r && a[b[pos[i] + ans]] == a[i]) ans++;
      }
      for (int i = x; i <= r; i++) {
        while (pos[i] - ans >= 0 && b[pos[i] - ans] >= l && a[b[pos[i] - ans]] == a[i]) ans++;
      }
    }
    std::cout << ans << "\n";
  }
  return 0;
}

// Author:  HolyK
// Created: Fri Aug 27 21:50:45 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}
inline char gc() {
  static constexpr int BufferSize = 1 << 22 | 5;
  static char buf[BufferSize], *p, *q;
  static std::streambuf *i = std::cin.rdbuf();
  return p == q ? p = buf, q = p + i->sgetn(p, BufferSize), p == q ? EOF : *p++ : *p++;
}
struct Reader {
  template <class T>
  Reader &operator>>(T &w) {
    char c, p = 0;
    for (; !std::isdigit(c = gc());) if (c == '-') p = 1;
    for (w = c & 15; std::isdigit(c = gc()); w = w * 10 + (c & 15)) ;
    if (p) w = -w;
    return *this;
  }
} cin;

using LL = long long;
using PII = std::pair<int, int>;
using u64 = uint64_t;
using u32 = uint32_t;
constexpr int N(5e5), T(8), P(32 / T), S(1 << P), B(32), L((N + B - 1) / B);
int n, m, k;
u32 a[N];
u64 pw[T + 1];
struct Info {
  u32 min, max, siz;
  u64 sum;
  Info &operator+=(const Info &r) {
    smin(min, r.min);
    smax(max, r.max);
    siz += r.siz;
    sum += r.sum;
    return *this;
  }
  void tag(const u32 &x) {
    min -= x, max -= x, sum -= u64(siz) * x;
  }
  void ins(const u32 &x) {
    smin(min, x), smax(max, x), siz++, sum += x;
  }
} t[L * 4][T];
u32 tag[L * 4][T];
u32 pos(u32 x) { return std::__lg(x) / P; }
constexpr Info Null = {~0U, 0U, 0U, 0ULL};
inline Info operator+(const Info &a, const Info &b) { return {std::min(a.min, b.min), std::max(a.max, b.max), a.siz + b.siz, a.sum + b.sum}; }
#define ls o << 1
#define rs o << 1 | 1
#define APPLY() for (int _ = 0; _ < T; _ += 4) F(_), F(_ + 1), F(_ + 2), F(_ + 3)
void pushup(int o) {
#define F(i) t[o][i] = t[ls][i] + t[rs][i]
  APPLY();
#undef F
}
void add(int o, int i, u32 z) {
  if (t[o][i].siz) {
    t[o][i].tag(z);
    tag[o][i] += z;
  }
}
void pushdown(int o) {
#define F(i) (tag[o][i] ? (add(ls, i, tag[o][i]), add(rs, i, tag[o][i]), tag[o][i] = 0) : 1)
  APPLY();
#undef F
}
u32 max, min;
u64 sum;
void ask(int o, int l, int r, int x, int y) {
  if (r - l == 1) {
    for (int i = l * B; i < r * B && i < n; i++) {
      a[i] -= tag[o][pos(a[i])];
    }
    memset(tag[o], 0, sizeof tag[o]);
    for (int i = x; i < y; i++) {
      smax(max, a[i]);
      smin(min, a[i]);
      sum += a[i];
    }
    return;
  }
  if (x <= l * B && r * B <= y) {
#define F(i) (smax(max, t[o][i].max), smin(min, t[o][i].min), sum += t[o][i].sum)
    APPLY();
#undef F
    // std::cerr << "range-ask: " << l << " " << r << " " << sum - pre << " ";    
    return;
  } 
  pushdown(o);
  int m = l + r >> 1;
  if (y <= m * B) {
    ask(ls, l, m, x, y);
  } else if (x >= m * B) {
    ask(rs, m, r, x, y);
  } else {
    ask(ls, l, m, x, m * B);
    ask(rs, m, r, m * B, y);
  }
}
void update(int o, int l, int r, int x, int y, u32 z, int bitl = 0, int bitr = T - 1) {

  while (bitl <= bitr && t[o][bitl].max <= z) bitl++;
  while (bitl <= bitr && t[o][bitr].max <= z) bitr--;
  if (bitl > bitr) return;
  if (r - l == 1) {
    for (int i = l * B; i < r * B && i < n; i++) {
      a[i] -= tag[o][pos(a[i])];
    }
    memset(tag[o], 0, sizeof tag[o]);
    // std::cerr << "update-single: ";
    for (int i = x; i < y; i++) {
      if (a[i] > z && a[i] < pw[bitr + 1]) {
        // std::cerr << i << " ";
        a[i] -= z;
      }
    }
    // std::cerr << "\n";
    std::fill(t[o], t[o] + T, Null);
    for (int i = l * B; i < r * B && i < n; i++) {
      t[o][pos(a[i])].ins(a[i]);
    } 
    return;
  }
  if (x <= l * B && r * B <= y) {
    for (; bitl <= bitr; bitr--) {
      const int &i = bitr;
      if (t[o][i].min > z && t[o][i].min - z >= pw[i]) {
        add(o, i, z);
        continue;
      }
      break;
    }
    if (bitl > bitr) {
      return;
    }
  }
  
  pushdown(o);
  int m = l + r >> 1;
  if (y <= m * B) {
    update(ls, l, m, x, y, z, bitl, bitr);
  } else if (x >= m * B) {
    update(rs, m, r, x, y, z, bitl, bitr);
  } else {
    update(ls, l, m, x, m * B, z, bitl, bitr);
    update(rs, m, r, m * B, y, z, bitl, bitr);
  }
  pushup(o);

}
void build(int o, int l, int r) {
  if (r - l == 1) {
    std::fill(t[o], t[o] + T, Null);
    int x = l * B, y = std::min(r * B, n);
    for (int i = x; i < y; i++) {
      t[o][pos(a[i])].ins(a[i]);
    }
    return;
  }
  int m = l + r >> 1;
  build(ls, l, m), build(rs, m, r);
  pushup(o);
}
int main() {
  // freopen("tt.in", "r", stdin);
  // freopen("t.out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  pw[0] = 1;
  for (int i = 1; i <= T; i++) pw[i] = pw[i - 1] * S;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  k = (n + B - 1) / B;
  std::cerr << "k = " << k << "\n";
  build(1, 0, k);
  int ans = 0;
  while (m--) {
    int opt, l, r;
    cin >> opt >> l >> r;
    l ^= ans, r ^= ans;
    assert(l <= r);
    l--;
    if (opt == 1) {
      u32 x;
      cin >> x;
      x ^= ans;
      update(1, 0, k, l, r, x);
    } else {
      max = 0U, min = ~0U, sum = 0ULL;
      ask(1, 0, k, l, r);
      ans = sum % (1 << 20);
      std::cout << sum << " " << min << " " << max << "\n";
    }
  }
  std::cerr << (double)clock() / CLOCKS_PER_SEC << "\n";
  return 0;
}

// Author:  HolyK
// Created: Wed Jul 14 11:25:19 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
inline char gc() {
  static constexpr int BufferSize = 1 << 22 | 5;
  static char buf[BufferSize], *p, *q;
  static std::streambuf *i = std::cin.rdbuf();
  return p == q ? p = buf, q = p + i->sgetn(p, BufferSize), p == q ? EOF : *p++ : *p++;
}
struct Reader {
  template <class T>
  Reader &operator>>(T &w) {
    char c, p = 0;
    for (; !std::isdigit(c = gc());) if (c == '-') p = 1;
    for (w = c & 15; std::isdigit(c = gc()); w = w * 10 + (c & 15)) ;
    if (p) w = -w;
    return *this;
  }
} cin;
// using std::cin;
template <class T>
struct Rec {
  std::vector<std::pair<T*, T>> rec;
  Rec(int n = 0) {
    rec.reserve(n);
  }
  void clear() { rec.clear(); }
  void operator()(T &x) {
    rec.emplace_back(&x, x);
  }
  void recover() {
    while (!rec.empty()) *rec.back().first = rec.back().second, rec.pop_back();
  }
};
constexpr int N(3e5 + 5), T(1024), S(N / T + 1);
struct Qry {
  int l, r, x, id;
  bool operator<(const Qry &rhs) const {
    return x < rhs.x || x == rhs.x && id < rhs.id;
  }
} q[N];
int n, m, tot;
PII a[N << 1];
int raw[N], val[N], b[N], pos[N], tmp[N];
LL f[N];
LL sum[S], ans[N];
int lp[S], rp[S], cnt[S];
bool vis[N];
struct Info {
  int l, r, x;
} rec[N];
int recs;
void ins(int l, int r, int z) {
  const int bl = l / T, br = r / T;
  if (bl == br) {
    sum[bl] += z * f[r - l + 1];
  } else if (z > 0) {
    rp[bl] = l, lp[br] = r;
  }
}
void add(int x) {
  if (b[x]) return;
  cnt[x / T]++;
  b[x] = 1;
  int l = x, r = x;
  if (x && b[x - 1]) {
    l = pos[x - 1];
    ins(pos[x - 1], x - 1, -1);
  }
  if (x + 1 < n && b[x + 1]) {
    r = pos[x + 1];
    ins(x + 1, pos[x + 1], -1);
  }
  pos[l] = r, pos[r] = l;
  ins(l, r, 1);
}
void add_rec(int x) {
  if (b[x]) return;
  cnt[x / T]++, b[x] = 1;
  int l = x, r = x;
  if (x && b[x - 1]) {
    l = pos[x - 1];
    ins(pos[x - 1], x - 1, -1);
  }
  if (x + 1 < n && b[x + 1]) {
    r = pos[x + 1];
    ins(x + 1, pos[x + 1], -1);
  }
  pos[l] = r, pos[r] = l;
  ins(l, r, 1);
  rec[++recs] = {l, r, x};
}
void recover() {
  // ri.recover(), rl.recover();
  while (recs) {
    auto &[l, r, x] = rec[recs--];
    cnt[x / T]--, b[x] = 0;
    ins(l, r, -1);
    if (l / T != r / T) rp[l / T] = lp[r / T] = -1;
    if (l < x) ins(l, x - 1, 1), pos[l] = x - 1, pos[x - 1] = l;
    if (x < r) ins(x + 1, r, 1), pos[r] = x + 1, pos[x + 1] = r;
  }
}

LL ask(int l, int r) {
  const int bl = l / T, br = r / T;
  LL ans = 0;
  if (bl == br) {
    int now = 0;
    for (int i = l; i <= r; i++) {
      if (b[i]) {
        now++;
      } else {
        ans += f[now];
        now = 0;
      }
    }
    return ans + f[now];
  }
  int y = bl * T + T, x = br * T, now = 0;
  for (int i = l; i < y; i++) {
    if (b[i]) {
      now++;
    } else {
      ans += f[now];
      now = 0;
    }
  }
  for (int i = bl + 1; i < br; i++, y += T) {
    if (T == cnt[i]) {
      now += T;
      continue;
    }
    if (~lp[i]) {
      now += lp[i] - y + 1;
    }
    ans += f[now] + sum[i];
    now = 0;
    if (~rp[i]) {
      now = y + T - rp[i];
    }
  }
  for (int i = x; i <= r; i++) {
    if (b[i]) {
      now++;
    } else {
      ans += f[now];
      now = 0;
    }
  }
  return ans + f[now];
};
int main() {
  f[0] = 0;
  for (int i = 1; i <= 3e5; i++) {
    f[i] = f[i - 1] + i;
  }
  double sta = (double)clock() / CLOCKS_PER_SEC;
#ifndef ONLINE_JUDGE
  freopen("t.in", "r", stdin);
  freopen("tt.out", "w", stdout);
#endif
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cin >> n >> m, tot = (n - 1) / T + 1;
  
  for (int i = 0; i < n; i++) {
    cin >> raw[i];
    a[i] = {raw[i], i};
  }
  
  int ta = n, tq = 0;
  for (int i = 0; i < m; i++) {
    int opt;
    cin >> opt >> q[i].l >> q[i].r;
    q[i].l--;
    q[i].id = i;
    if (opt == 2) {
      cin >> q[i].x;
      q[i].r--;
      tq++;
    } else {
      a[ta++] = {q[i].r, q[i].l};
      ans[i] = -1;
    }
  }
  std::sort(a, a + ta);
  for (int i = 0, r, d; i < m; i = r) {
    for (; i < m && !q[i].x; i++) {
      raw[q[i].l] = q[i].r;;
    }
    r = std::min(m, i + 1324);
    // for (int k = step; r < m && k; r++) k -= !q[r].x;
    std::sort(q + i, q + r);
    for (d = i; d < r && !q[d].x; d++) ;
    // assert(d - i <= step);
    for (int j = 0; j < n; j++) {
      pos[j] = -1;
      b[j] = 0;
      vis[j] = 0;
      val[j] = raw[j];
    }
   for (int j = 0; j < tot; j++) {
      sum[j] = 0;
      cnt[j] = 0;
      lp[j] = rp[j] = -1;
    }
    for (int j = i; j < d; j++) {
      vis[q[j].l] = 1;
    }
    tmp[0] = 0;
    for (int j = 0; j < n; j++) if (vis[j]) tmp[++tmp[0]] = j;
    for (int j = d, k = 0; j < r; j++) {
      auto [ql, qr, x, id] = q[j];
      for (; k < ta && a[k].first <= x; k++) {
        if (val[a[k].second] != a[k].first || vis[a[k].second]) continue;
        add(a[k].second);
      }
      for (int t = i; t < d; t++) {
        if (q[t].id > id) continue;
        val[q[t].l] = q[t].r;
      }
      for (int t = 1; t <= tmp[0]; t++) {
        if (val[tmp[t]] <= x) add_rec(tmp[t]);
      }
      ans[id] = ask(ql, qr);
      for (int t = 1; t <= tmp[0]; t++) {
        val[tmp[t]] = raw[tmp[t]];
      }
      recover();
    }
    for (int j = i; j < d; j++) {
      raw[q[j].l] = q[j].r;
    }
  }
  for (int i = 0; i < m; i++) if (~ans[i]) std::cout << ans[i] << "\n";
  std::cerr << "time : " << (double)clock() / CLOCKS_PER_SEC - sta << "\n";
  return 0;
}

// Author:  HolyK
// Created: Wed Sep  8 16:32:52 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(1e5 + 5), T(384);
int n, m, a[N];
struct Qry {
  int l, r, p, id;
  bool operator<(const Qry &rhs) const {
    return l / T == rhs.l / T ? l / T & 1 ? r < rhs.r : r > rhs.r : l < rhs.l;
  }
} q[N];

int cnt[N];
LL s, sum[N];
void add(int x) {
  if (!cnt[x]) s += x;
  sum[cnt[x]] -= x;
  sum[++cnt[x]] += x;
}
void del(int x) {
  sum[cnt[x]] -= x;
  sum[--cnt[x]] += x;
  if (!cnt[x]) s -= x;
}
std::vector<int> big;
int ans[N], pw[T], ppw[T];
int main() {
  // freopen("t.in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    cnt[a[i]]++;
  }
  for (int i = 1; i <= 1e5; i++) {
    if (cnt[i] >= T) {
      big.push_back(i);
    }
  }
  for (int i = 1; i <= m; i++) {
    std::cin >> q[i].l >> q[i].r >> q[i].p;
    q[i].id = i;
  }
  std::sort(q + 1, q + 1 + m);
  memset(cnt, 0, sizeof cnt);
  for (int i = 1, x = 1, y = 0; i <= m; i++) {
    while (x > q[i].l) add(a[--x]);
    while (y < q[i].r) add(a[++y]);
    while (x < q[i].l) del(a[x++]);
    while (y > q[i].r) del(a[y--]);
    int len = q[i].r - q[i].l + 1;
    // std::cerr << "[Q] " << q[i].l << " " << q[i].r << ":\n";
    pw[0] = 1;
    const int &p = q[i].p;
    for (int i = 1; i < T; i++) pw[i] = 2LL * pw[i - 1] % p;
    ppw[0] = 1;
    ppw[1] = pw[T - 1] * 2LL % p;
    for (int i = 2; i < T; i++) ppw[i] = 1LL * ppw[i - 1] * ppw[1] % p;
    auto power = [&](int k) {
      return 1LL * ppw[k / T] * pw[k % T] % p;
    };
    auto &r = ans[q[i].id];
    // std::cerr << s << "\n";
    r = s % p * power(len) % p;
    for (int x : big) {
      if (cnt[x] >= T) {
        r = (r - 1LL * x * power(len - cnt[x])) % p;
      }
    }
    for (int i = std::min(T - 1, len), c = power(len - i); i; i--, c = 2LL * c % p) {
      if (sum[i]) {
        r = (r - sum[i] % p * c) % p;
      }
    }
    if (r < 0) r += p;
  }
  for (int i = 1; i <= m; i++) {
    std::cout << ans[i] << "\n";
  }
  return 0;
}

// Author:  HolyK
// Created: Thu Sep 16 08:09:38 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(1e5 + 5), T(512), S(N / T + 1);

template <int S>
struct LazyArray {
  int a[S], b[S], c;
  void clear() { c++; }
  int &operator[](const int &i) {
    if (b[i] != c) b[i] = c, a[i] = 0;
    return a[i];
  } 
};
int n, m, a[N], s[N];

std::vector<int> g[N], h[N];
int id[N], cnt, trash[N], *cur = trash, val[N], ans[S][N];
int newId() {
  return trash == cur ? ++cnt : *cur--;
}
void del(int x) {
  if (!id[x]) return;
  *++cur = id[x];
  memset(ans[id[x]], 0x3f, sizeof ans[id[x]]);
  val[id[x]] = 0;
  id[x] = 0;
}


int cal(const std::vector<int> &a, const std::vector<int> &b) {
  int res = 1e9;
  for (int i = 0, j = 0; i < a.size() || j < b.size(); ) {
    if (j == b.size() || i < a.size() && a[i] < b[j]) {
      if (j) smin(res, a[i] - b[j - 1]);
      i++;
    } else {
      if (i) smin(res, b[j] - a[i - 1]);
      j++;
    }
  }
  return res;
}

int fa[N], root[N];
int find(int x) {
  while (x != fa[x]) x = fa[x] = fa[fa[x]];
  return x;
}
void update(int x) {
  int y = id[x];
  for (int i = 1, p = 0; i <= n; i++) {
    a[i] = a[find(i)];
    if (a[i] == x) {
      p = i;
    } else if (p) {
      smin(ans[y][a[i]], i - p);
    }
  }
  for (int i = n, p = 0; i; i--) {
    if (a[i] == x) {
      p = i;
    } else if (p) {
      smin(ans[y][a[i]], p - i);
    }
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> m;
  
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    s[a[i]]++;
  }

  for (int i = 1; i <= 1e5; i++) {
    if (s[i] >= T) {
      id[i] = newId();
      val[id[i]] = i;
    }
  }
  
  for (int i = 1; i <= n; i++) {
    if (s[a[i]] < T) g[a[i]].push_back(i);
    root[a[i]] = i;
  }

  for (int i = 1; i <= n; i++) {
    fa[i] = root[a[i]];
  }
  
  memset(ans, 0x3f, sizeof ans);
  for (int i = 1; i <= cnt; i++) {
    update(val[i]);
  }
  
  int res = 0;
  while (m--) {
    int opt, x, y;
    std::cin >> opt >> x >> y;
    x ^= res, y ^= res;
    static int tmp[N];
    
    auto mergeTo = [&](std::vector<int> &a, std::vector<int> &b) {
      std::merge(a.begin(), a.end(), b.begin(), b.end(), tmp);
      b.resize(a.size() + b.size());
      a.clear();
      std::copy_n(tmp, b.size(), b.begin());
    };
    // std::cerr << x << " " << y << " " << s[x] << " " << s[y] << "\n";
    if (opt == 1) {
      if (x == y || !s[x]) continue;
      if (!root[y]) {
        root[y] = root[x];
        a[root[y]] = y;
      } else {
        fa[root[x]] = root[y];
      }
      root[x] = 0;
      for (int i = 1; i <= cnt; i++) {
        smin(ans[i][y], ans[i][x]);
        ans[i][x] = 0x3f3f3f3f;
      }
      if (s[x] < T && s[y] < T) {
        s[y] += s[x], s[x] = 0;
        if (s[y] >= T) {
          id[y] = newId();
          val[id[y]] = y;
          g[x].clear(), g[y].clear();
          
          update(y);
          
        } else {
          mergeTo(g[x], g[y]);
        }
        continue;
      }
      
      if (s[x] >= T && s[y] < T || s[x] < T && s[y] >= T) {
        if (s[x] > s[y]) {
          std::swap(s[x], s[y]);
          std::swap(id[x], id[y]);
          std::swap(g[x], g[y]);
          std::swap(h[x], h[y]);
          val[id[y]] = y;
        }
        if (h[y].size() + s[x] < T) {
          s[y] += s[x], s[x] = 0;
          mergeTo(g[x], h[y]);
          continue;
        }
      }
      g[x].clear(), g[y].clear();
      h[x].clear(), h[y].clear(); 
      del(x);
      s[y] += s[x], s[x] = 0;
      update(y);
    } else {
      if (!s[x] || !s[y]) {
        res = 0;
        std::cout << "Ikaros\n";
        continue;
      }
      if (x == y) {
        res = 0;
        std::cout << "0\n";
        continue;
      }
      if (s[x] < T && s[y] < T) {
        res = cal(g[x], g[y]);
      } else if (s[x] >= T && s[y] >= T) {
        res = std::min(ans[id[x]][y], ans[id[y]][x]);
        smin(res, cal(h[x], h[y]));
      } else {
        if (s[x] < s[y]) std::swap(x, y);
        res = ans[id[x]][y];
        smin(res, cal(h[x], g[y]));
      }
      std::cout << res << "\n";
    }
  }
  return 0;
}