#include <bits/stdc++.h>
using namespace std;
int hd[400007], pre[400007], to[400007], num, dfn[400007], rk[400007], ord,
    st[400007][23], dep[400007], rf[400007], ts, mins, rt;
int a[400007], pos[400007], lg[400007], n, m;
long long dp[400007], w[400007];
bool use[400007];
vector<int> id[400007];
vector<long long> dis[400007], fdis[400007];
void adde(int x, int y, int z) {
  num++;
  pre[num] = hd[x];
  hd[x] = num;
  to[num] = y;
  w[num] = z;
}
void dfs1(int v, int f) {
  int i, u;
  dep[v] = dep[f] + 1;
  dfn[++ord] = v, rk[v] = ord;
  for (i = hd[v]; i; i = pre[i]) {
    u = to[i];
    if (u == f) continue;
    dp[u] = dp[v] + w[i];
    dfs1(u, v);
    dfn[++ord] = v;
  }
}
int dmin(int x, int y) { return dep[x] < dep[y] ? x : y; }
void mak_st() {
  int i, j;
  lg[0] = -1;
  ;
  for (i = 1; i <= ord; i++) lg[i] = lg[i / 2] + 1;
  for (i = 1; i <= ord; i++) st[i][0] = dfn[i];
  for (j = 1; j <= 20; j++)
    for (i = 1; i <= (ord - (1 << j) + 1); i++)
      st[i][j] = dmin(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int glca(int x, int y) {
  x = rk[x], y = rk[y];
  if (x > y) swap(x, y);
  int l = lg[y - x + 1];
  return dmin(st[x][l], st[y - (1 << l) + 1][l]);
}
long long dist(int x, int y) { return dp[x] + dp[y] - 2 * dp[glca(x, y)]; }
void getts(int v, int f) {
  int i, u;
  ts++;
  for (i = hd[v]; i; i = pre[i]) {
    u = to[i];
    if (u == f || use[u]) continue;
    getts(u, v);
  }
}
int getrt(int v, int f) {
  int i, u;
  int ms = 0, sz = 1;
  for (i = hd[v]; i; i = pre[i]) {
    u = to[i];
    if (u == f || use[u]) continue;
    int s = getrt(u, v);
    sz += s;
    ms = max(s, ms);
  }
  ms = max(ms, ts - sz);
  if (ms < mins) mins = ms, rt = v;
  return sz;
}
void add(int v, int f) {
  int i, u;
  id[rt].push_back(v);
  for (i = hd[v]; i; i = pre[i]) {
    u = to[i];
    if (u == f || use[u]) continue;
    add(u, v);
  }
}
bool cmp(int x, int y) { return pos[x] < pos[y]; }
void solve(int v, int f) {
  int i;
  ts = 0, getts(v, 0);
  rt = 0, mins = n + 1, getrt(v, 0);
  v = rt;
  add(v, 0);
  sort(id[v].begin(), id[v].end(), cmp);
  int s = id[v].size();
  for (i = 0; i < s; i++) {
    int u = id[v][i];
    dis[v].push_back(dist(u, v));
    fdis[v].push_back(f ? dist(u, f) : 0);
  }
  for (i = 1; i < s; i++) {
    dis[v][i] += dis[v][i - 1];
    fdis[v][i] += fdis[v][i - 1];
  }
  rf[v] = f;
  use[v] = true;
  for (i = hd[v]; i; i = pre[i])
    if (!use[to[i]]) solve(to[i], v);
}
long long query(int v, int l, int r) {
  long long ans = 0;
  int p = v;
  while (v) {
    int f = rf[v];
    int nl = lower_bound(id[v].begin(), id[v].end(), a[l], cmp) - id[v].begin();
    int nr = upper_bound(id[v].begin(), id[v].end(), a[r], cmp) - id[v].begin();
    if (nr) {
      ans += dis[v][nr - 1] - fdis[v][nr - 1];
      if (nl) ans -= dis[v][nl - 1] - fdis[v][nl - 1];
      ans += (nr - nl) * dist(p, v);
      if (f) ans -= (nr - nl) * dist(p, f);
    }
    v = rf[v];
  }
  return ans;
}
void modify(int v, int x) {
  while (v) {
    int p = lower_bound(id[v].begin(), id[v].end(), a[x], cmp) - id[v].begin();
    if (p != id[v].size() - 1 && id[v][p + 1] == a[x + 1]) {
      dis[v][p] = dis[v][p + 1] - dis[v][p];
      fdis[v][p] = fdis[v][p + 1] - fdis[v][p];
      if (p) {
        dis[v][p] += dis[v][p - 1];
        fdis[v][p] += fdis[v][p - 1];
      }
      swap(id[v][p], id[v][p + 1]);
    }
    v = rf[v];
  }
}
int read() {
  int x;
  char c;
  while ((c = getchar()) < 48 || c > 57)
    ;
  x = c - 48;
  while ((c = getchar()) >= 48 && c <= 57) x = x * 10 + c - 48;
  return x;
}
int main() {
  int i, x, y, z, op;
  int mod = 1 << 30;
  long long lans = 0;
  n = read(), m = read();
  for (i = 1; i <= n; i++) a[i] = read(), pos[a[i]] = i;
  for (i = 1; i < n; i++) {
    x = read(), y = read(), z = read();
    adde(x, y, z), adde(y, x, z);
  }
  dfs1(1, 0);
  mak_st();
  solve(1, 0);
  for (i = 1; i <= m; i++) {
    op = read(), x = read();
    int val = lans % mod;
    if (op == 1) {
      y = read(), z = read();
      x = val ^ x, y = val ^ y, z = val ^ z;
      printf("%lld\n", lans = query(z, x, y));
    } else {
      x ^= val;
      modify(a[x], x);
      pos[a[x]] = x + 1;
      pos[a[x + 1]] = x;
      swap(a[x], a[x + 1]);
    }
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

Whoa! You did a great job helping Team Rocket who managed to capture all the Pokemons sent by Bash. Meowth, part of Team Rocket, having already mastered the human language, now wants to become a master in programming as well. He agrees to free the Pokemons if Bash can answer his questions.

Initially, Meowth gives Bash a weighted tree containing n nodes and a sequence a1, a2..., an which is a permutation of 1, 2, ..., n. Now, Mewoth makes q queries of one of the following forms:

  * 1 l r v: meaning Bash should report <image>, where dist(a, b) is the length of the shortest path from node a to node b in the given tree. 
  * 2 x: meaning Bash should swap ax and ax + 1 in the given sequence. This new sequence is used for later queries. 



Help Bash to answer the questions!

Input

The first line contains two integers n and q (1 ≤ n ≤ 2·105, 1 ≤ q ≤ 2·105) — the number of nodes in the tree and the number of queries, respectively.

The next line contains n space-separated integers — the sequence a1, a2, ..., an which is a permutation of 1, 2, ..., n.

Each of the next n - 1 lines contain three space-separated integers u, v, and w denoting that there exists an undirected edge between node u and node v of weight w, (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 106). It is guaranteed that the given graph is a tree.

Each query consists of two lines. First line contains single integer t, indicating the type of the query. Next line contains the description of the query: 

  * t = 1: Second line contains three integers a, b and c (1 ≤ a, b, c < 230) using which l, r and v can be generated using the formula given below: 
    * <image>, 
    * <image>, 
    * <image>. 
  * t = 2: Second line contains single integer a (1 ≤ a < 230) using which x can be generated using the formula given below: 
    * <image>. 



The ansi is the answer for the i-th query, assume that ans0 = 0. If the i-th query is of type 2 then ansi = ansi - 1. It is guaranteed that: 

  * for each query of type 1: 1 ≤ l ≤ r ≤ n, 1 ≤ v ≤ n, 
  * for each query of type 2: 1 ≤ x ≤ n - 1. 



The <image> operation means bitwise exclusive OR.

Output

For each query of type 1, output a single integer in a separate line, denoting the answer to the query.

Example

Input

5 5
4 5 1 3 2
4 2 4
1 3 9
4 1 4
4 5 2
1
1 5 4
1
22 20 20
2
38
2
39
1
36 38 38


Output

23
37
28

Note

In the sample, the actual queries are the following: 

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int hd[400007], pre[400007], to[400007], num, dfn[400007], rk[400007], ord,
    st[400007][23], dep[400007], rf[400007], ts, mins, rt;
int a[400007], pos[400007], lg[400007], n, m;
long long dp[400007], w[400007];
bool use[400007];
vector<int> id[400007];
vector<long long> dis[400007], fdis[400007];
void adde(int x, int y, int z) {
  num++;
  pre[num] = hd[x];
  hd[x] = num;
  to[num] = y;
  w[num] = z;
}
void dfs1(int v, int f) {
  int i, u;
  dep[v] = dep[f] + 1;
  dfn[++ord] = v, rk[v] = ord;
  for (i = hd[v]; i; i = pre[i]) {
    u = to[i];
    if (u == f) continue;
    dp[u] = dp[v] + w[i];
    dfs1(u, v);
    dfn[++ord] = v;
  }
}
int dmin(int x, int y) { return dep[x] < dep[y] ? x : y; }
void mak_st() {
  int i, j;
  lg[0] = -1;
  ;
  for (i = 1; i <= ord; i++) lg[i] = lg[i / 2] + 1;
  for (i = 1; i <= ord; i++) st[i][0] = dfn[i];
  for (j = 1; j <= 20; j++)
    for (i = 1; i <= (ord - (1 << j) + 1); i++)
      st[i][j] = dmin(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int glca(int x, int y) {
  x = rk[x], y = rk[y];
  if (x > y) swap(x, y);
  int l = lg[y - x + 1];
  return dmin(st[x][l], st[y - (1 << l) + 1][l]);
}
long long dist(int x, int y) { return dp[x] + dp[y] - 2 * dp[glca(x, y)]; }
void getts(int v, int f) {
  int i, u;
  ts++;
  for (i = hd[v]; i; i = pre[i]) {
    u = to[i];
    if (u == f || use[u]) continue;
    getts(u, v);
  }
}
int getrt(int v, int f) {
  int i, u;
  int ms = 0, sz = 1;
  for (i = hd[v]; i; i = pre[i]) {
    u = to[i];
    if (u == f || use[u]) continue;
    int s = getrt(u, v);
    sz += s;
    ms = max(s, ms);
  }
  ms = max(ms, ts - sz);
  if (ms < mins) mins = ms, rt = v;
  return sz;
}
void add(int v, int f) {
  int i, u;
  id[rt].push_back(v);
  for (i = hd[v]; i; i = pre[i]) {
    u = to[i];
    if (u == f || use[u]) continue;
    add(u, v);
  }
}
bool cmp(int x, int y) { return pos[x] < pos[y]; }
void solve(int v, int f) {
  int i;
  ts = 0, getts(v, 0);
  rt = 0, mins = n + 1, getrt(v, 0);
  v = rt;
  add(v, 0);
  sort(id[v].begin(), id[v].end(), cmp);
  int s = id[v].size();
  for (i = 0; i < s; i++) {
    int u = id[v][i];
    dis[v].push_back(dist(u, v));
    fdis[v].push_back(f ? dist(u, f) : 0);
  }
  for (i = 1; i < s; i++) {
    dis[v][i] += dis[v][i - 1];
    fdis[v][i] += fdis[v][i - 1];
  }
  rf[v] = f;
  use[v] = true;
  for (i = hd[v]; i; i = pre[i])
    if (!use[to[i]]) solve(to[i], v);
}
long long query(int v, int l, int r) {
  long long ans = 0;
  int p = v;
  while (v) {
    int f = rf[v];
    int nl = lower_bound(id[v].begin(), id[v].end(), a[l], cmp) - id[v].begin();
    int nr = upper_bound(id[v].begin(), id[v].end(), a[r], cmp) - id[v].begin();
    if (nr) {
      ans += dis[v][nr - 1] - fdis[v][nr - 1];
      if (nl) ans -= dis[v][nl - 1] - fdis[v][nl - 1];
      ans += (nr - nl) * dist(p, v);
      if (f) ans -= (nr - nl) * dist(p, f);
    }
    v = rf[v];
  }
  return ans;
}
void modify(int v, int x) {
  while (v) {
    int p = lower_bound(id[v].begin(), id[v].end(), a[x], cmp) - id[v].begin();
    if (p != id[v].size() - 1 && id[v][p + 1] == a[x + 1]) {
      dis[v][p] = dis[v][p + 1] - dis[v][p];
      fdis[v][p] = fdis[v][p + 1] - fdis[v][p];
      if (p) {
        dis[v][p] += dis[v][p - 1];
        fdis[v][p] += fdis[v][p - 1];
      }
      swap(id[v][p], id[v][p + 1]);
    }
    v = rf[v];
  }
}
int read() {
  int x;
  char c;
  while ((c = getchar()) < 48 || c > 57)
    ;
  x = c - 48;
  while ((c = getchar()) >= 48 && c <= 57) x = x * 10 + c - 48;
  return x;
}
int main() {
  int i, x, y, z, op;
  int mod = 1 << 30;
  long long lans = 0;
  n = read(), m = read();
  for (i = 1; i <= n; i++) a[i] = read(), pos[a[i]] = i;
  for (i = 1; i < n; i++) {
    x = read(), y = read(), z = read();
    adde(x, y, z), adde(y, x, z);
  }
  dfs1(1, 0);
  mak_st();
  solve(1, 0);
  for (i = 1; i <= m; i++) {
    op = read(), x = read();
    int val = lans % mod;
    if (op == 1) {
      y = read(), z = read();
      x = val ^ x, y = val ^ y, z = val ^ z;
      printf("%lld\n", lans = query(z, x, y));
    } else {
      x ^= val;
      modify(a[x], x);
      pos[a[x]] = x + 1;
      pos[a[x + 1]] = x;
      swap(a[x], a[x + 1]);
    }
  }
  return 0;
}

```