#include <bits/stdc++.h>
using namespace std;
int A, n, m, p, h[200001], rt, now, maxsz[200001], sz[200001], vis[200001],
    num[200001], id[200001], c[200001];
long long ans;
struct line {
  int to, ne, v;
} a[400001];
inline void add(int x, int y, int z) {
  a[++p].to = y;
  a[p].ne = h[x];
  a[p].v = z;
  h[x] = p;
}
void findrt(int x, int fa, int tot) {
  sz[x] = 1;
  maxsz[x] = 0;
  for (int i = h[x]; i; i = a[i].ne) {
    if (vis[a[i].to] || a[i].to == fa) continue;
    findrt(a[i].to, x, tot);
    sz[x] += sz[a[i].to];
    maxsz[x] = max(maxsz[x], sz[a[i].to]);
  }
  maxsz[x] = max(maxsz[x], tot - sz[x]);
  if (maxsz[x] < maxsz[now]) now = x;
}
vector<int> f[200001];
vector<long long> d[200001];
vector<pair<int, long long> > tot1[200001], tot2[200001];
vector<pair<int, int> > Size[200001];
pair<int, long long> g[200001];
pair<int, int> gg[200001];
void work(int x, int fa, int rt) {
  Size[rt].push_back(make_pair(id[x], 1));
  sz[x] = 1;
  for (int i = h[x]; i; i = a[i].ne) {
    if (vis[a[i].to] || a[i].to == fa) continue;
    work(a[i].to, x, rt);
    sz[x] += sz[a[i].to];
  }
}
void gx(int x, int fa, int now, int rt, long long dep) {
  d[x].push_back(dep);
  f[x].push_back(rt);
  tot2[now].push_back(make_pair(id[x], dep));
  tot1[rt].push_back(make_pair(id[x], dep));
  for (int i = h[x]; i; i = a[i].ne) {
    if (vis[a[i].to] || a[i].to == fa) continue;
    gx(a[i].to, x, now, rt, dep + a[i].v);
  }
}
bool cmp(int a, int b) { return Size[now][a].first < Size[now][b].first; }
void dfs(int x) {
  vis[x] = 1;
  work(x, 0, x);
  f[x].push_back(x);
  d[x].push_back(0);
  int z[Size[x].size()];
  for (int i = 0; i < Size[x].size(); i++) z[i] = i;
  memcpy(gg, &Size[x][0], sizeof(Size[x][0]) * Size[x].size());
  sort(z, z + Size[x].size(), cmp);
  for (int i = 0; i < Size[x].size(); i++) Size[x][i] = gg[z[i]];
  for (int i = 1; i < Size[x].size(); i++)
    Size[x][i].second += Size[x][i - 1].second;
  tot1[x].push_back(make_pair(id[x], 0));
  for (int i = h[x]; i; i = a[i].ne) {
    if (vis[a[i].to]) continue;
    now = 0;
    findrt(a[i].to, x, sz[a[i].to]);
    gx(a[i].to, x, now, x, a[i].v);
    sort(tot2[now].begin(), tot2[now].end());
    for (int j = 1; j < tot2[now].size(); j++)
      tot2[now][j].second += tot2[now][j - 1].second;
    dfs(now);
  }
  memcpy(g, &tot1[x][0], sizeof(tot1[x][0]) * tot1[x].size());
  for (int i = 0; i < Size[x].size(); i++) tot1[x][i] = g[z[i]];
  for (int i = 1; i < tot1[x].size(); i++)
    tot1[x][i].second += tot1[x][i - 1].second;
}
inline int erfen(const vector<pair<int, long long> > &x, int k) {
  if (x[x.size() - 1].first <= k) return x.size();
  int l = 0, r = x.size() - 1, mid;
  while (l < r) {
    mid = (l + r) >> 1;
    if (x[mid].first > k)
      r = mid;
    else
      l = mid + 1;
  }
  return l;
}
inline long long ask(const vector<pair<int, long long> > &x, int l, int r) {
  int fr = erfen(x, r), fl = erfen(x, l - 1);
  if (!fr) return 0;
  fr--;
  if (!fl) return x[fr].second;
  fl--;
  return x[fr].second - x[fl].second;
}
inline long long ask(const vector<pair<int, long long> > &x,
                     const vector<pair<int, int> > &y, int l, int r,
                     long long k) {
  int fr = erfen(x, r), fl = erfen(x, l - 1);
  if (!fr) return 0;
  fr--;
  if (!fl) return x[fr].second + k * y[fr].second;
  fl--;
  return x[fr].second - x[fl].second + k * (y[fr].second - y[fl].second);
}
inline long long ask(int x, int l, int r) {
  long long ans = ask(tot1[x], l, r);
  for (int i = f[x].size() - 2; ~i; i--) {
    ans += ask(tot1[f[x][i]], Size[f[x][i]], l, r, d[x][i]);
    ans -= ask(tot2[f[x][i + 1]], Size[f[x][i + 1]], l, r, d[x][i]);
  }
  return ans;
}
inline int read() {
  int x = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x;
}
void update(int x, int y) {
  int fx, fy;
  for (int i = f[y].size() - 1; ~i; i--) {
    fy = erfen(tot1[f[y][i]], id[y]);
    fy -= 2;
    if ((~fy) && tot1[f[y][i]][fy].first == id[x]) break;
    fy++;
    tot1[f[y][i]][fy].first--, Size[f[y][i]][fy].first--;
  }
  for (int i = f[y].size() - 1; i; i--) {
    fy = erfen(tot2[f[y][i]], id[y]);
    fy -= 2;
    if ((~fy) && tot2[f[y][i]][fy].first == id[x]) break;
    fy++;
    tot2[f[y][i]][fy].first--;
  }
  for (int i = f[x].size() - 1; ~i; i--) {
    fx = erfen(tot1[f[x][i]], id[x]);
    if ((fx ^ tot1[f[x][i]].size()) && tot1[f[x][i]][fx].first == id[y]) {
      tot1[f[x][i]][fx - 1].second = tot1[f[x][i]][fx].second - d[x][i];
    } else {
      fx--;
      tot1[f[x][i]][fx].first++, Size[f[x][i]][fx].first++;
    }
  }
  for (int i = f[x].size() - 1; i; i--) {
    fx = erfen(tot2[f[x][i]], id[x]);
    if ((fx ^ tot1[f[x][i]].size()) && tot2[f[x][i]][fx].first == id[y]) {
      tot2[f[x][i]][fx - 1].second = tot2[f[x][i]][fx].second - d[x][i - 1];
    } else {
      fx--;
      tot2[f[x][i]][fx].first++;
    }
  }
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) c[i] = read(), id[c[i]] = i;
  for (int i = 1; i < n; i++) {
    int x = read(), y = read(), z = read();
    add(x, y, z);
    add(y, x, z);
  }
  maxsz[0] = 1e9 + 10;
  findrt(1, 0, n);
  rt = now;
  dfs(now);
  while (m--) {
    int mode, x, y, z;
    scanf("%d", &mode);
    if (mode == 1) {
      scanf("%d%d%d", &x, &y, &z);
      x ^= ans;
      y ^= ans;
      z ^= ans;
      ans = ask(z, x, y);
      printf("%lld\n", ans);
      ans &= (1 << 30) - 1;
    } else {
      scanf("%d", &x);
      x ^= ans;
      update(c[x], c[x + 1]);
      id[c[x]]++;
      id[c[x + 1]]--;
      swap(c[x], c[x + 1]);
    }
  }
  return 0;
}

### Prompt

Please create a solution in Cpp to 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 A, n, m, p, h[200001], rt, now, maxsz[200001], sz[200001], vis[200001],
    num[200001], id[200001], c[200001];
long long ans;
struct line {
  int to, ne, v;
} a[400001];
inline void add(int x, int y, int z) {
  a[++p].to = y;
  a[p].ne = h[x];
  a[p].v = z;
  h[x] = p;
}
void findrt(int x, int fa, int tot) {
  sz[x] = 1;
  maxsz[x] = 0;
  for (int i = h[x]; i; i = a[i].ne) {
    if (vis[a[i].to] || a[i].to == fa) continue;
    findrt(a[i].to, x, tot);
    sz[x] += sz[a[i].to];
    maxsz[x] = max(maxsz[x], sz[a[i].to]);
  }
  maxsz[x] = max(maxsz[x], tot - sz[x]);
  if (maxsz[x] < maxsz[now]) now = x;
}
vector<int> f[200001];
vector<long long> d[200001];
vector<pair<int, long long> > tot1[200001], tot2[200001];
vector<pair<int, int> > Size[200001];
pair<int, long long> g[200001];
pair<int, int> gg[200001];
void work(int x, int fa, int rt) {
  Size[rt].push_back(make_pair(id[x], 1));
  sz[x] = 1;
  for (int i = h[x]; i; i = a[i].ne) {
    if (vis[a[i].to] || a[i].to == fa) continue;
    work(a[i].to, x, rt);
    sz[x] += sz[a[i].to];
  }
}
void gx(int x, int fa, int now, int rt, long long dep) {
  d[x].push_back(dep);
  f[x].push_back(rt);
  tot2[now].push_back(make_pair(id[x], dep));
  tot1[rt].push_back(make_pair(id[x], dep));
  for (int i = h[x]; i; i = a[i].ne) {
    if (vis[a[i].to] || a[i].to == fa) continue;
    gx(a[i].to, x, now, rt, dep + a[i].v);
  }
}
bool cmp(int a, int b) { return Size[now][a].first < Size[now][b].first; }
void dfs(int x) {
  vis[x] = 1;
  work(x, 0, x);
  f[x].push_back(x);
  d[x].push_back(0);
  int z[Size[x].size()];
  for (int i = 0; i < Size[x].size(); i++) z[i] = i;
  memcpy(gg, &Size[x][0], sizeof(Size[x][0]) * Size[x].size());
  sort(z, z + Size[x].size(), cmp);
  for (int i = 0; i < Size[x].size(); i++) Size[x][i] = gg[z[i]];
  for (int i = 1; i < Size[x].size(); i++)
    Size[x][i].second += Size[x][i - 1].second;
  tot1[x].push_back(make_pair(id[x], 0));
  for (int i = h[x]; i; i = a[i].ne) {
    if (vis[a[i].to]) continue;
    now = 0;
    findrt(a[i].to, x, sz[a[i].to]);
    gx(a[i].to, x, now, x, a[i].v);
    sort(tot2[now].begin(), tot2[now].end());
    for (int j = 1; j < tot2[now].size(); j++)
      tot2[now][j].second += tot2[now][j - 1].second;
    dfs(now);
  }
  memcpy(g, &tot1[x][0], sizeof(tot1[x][0]) * tot1[x].size());
  for (int i = 0; i < Size[x].size(); i++) tot1[x][i] = g[z[i]];
  for (int i = 1; i < tot1[x].size(); i++)
    tot1[x][i].second += tot1[x][i - 1].second;
}
inline int erfen(const vector<pair<int, long long> > &x, int k) {
  if (x[x.size() - 1].first <= k) return x.size();
  int l = 0, r = x.size() - 1, mid;
  while (l < r) {
    mid = (l + r) >> 1;
    if (x[mid].first > k)
      r = mid;
    else
      l = mid + 1;
  }
  return l;
}
inline long long ask(const vector<pair<int, long long> > &x, int l, int r) {
  int fr = erfen(x, r), fl = erfen(x, l - 1);
  if (!fr) return 0;
  fr--;
  if (!fl) return x[fr].second;
  fl--;
  return x[fr].second - x[fl].second;
}
inline long long ask(const vector<pair<int, long long> > &x,
                     const vector<pair<int, int> > &y, int l, int r,
                     long long k) {
  int fr = erfen(x, r), fl = erfen(x, l - 1);
  if (!fr) return 0;
  fr--;
  if (!fl) return x[fr].second + k * y[fr].second;
  fl--;
  return x[fr].second - x[fl].second + k * (y[fr].second - y[fl].second);
}
inline long long ask(int x, int l, int r) {
  long long ans = ask(tot1[x], l, r);
  for (int i = f[x].size() - 2; ~i; i--) {
    ans += ask(tot1[f[x][i]], Size[f[x][i]], l, r, d[x][i]);
    ans -= ask(tot2[f[x][i + 1]], Size[f[x][i + 1]], l, r, d[x][i]);
  }
  return ans;
}
inline int read() {
  int x = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x;
}
void update(int x, int y) {
  int fx, fy;
  for (int i = f[y].size() - 1; ~i; i--) {
    fy = erfen(tot1[f[y][i]], id[y]);
    fy -= 2;
    if ((~fy) && tot1[f[y][i]][fy].first == id[x]) break;
    fy++;
    tot1[f[y][i]][fy].first--, Size[f[y][i]][fy].first--;
  }
  for (int i = f[y].size() - 1; i; i--) {
    fy = erfen(tot2[f[y][i]], id[y]);
    fy -= 2;
    if ((~fy) && tot2[f[y][i]][fy].first == id[x]) break;
    fy++;
    tot2[f[y][i]][fy].first--;
  }
  for (int i = f[x].size() - 1; ~i; i--) {
    fx = erfen(tot1[f[x][i]], id[x]);
    if ((fx ^ tot1[f[x][i]].size()) && tot1[f[x][i]][fx].first == id[y]) {
      tot1[f[x][i]][fx - 1].second = tot1[f[x][i]][fx].second - d[x][i];
    } else {
      fx--;
      tot1[f[x][i]][fx].first++, Size[f[x][i]][fx].first++;
    }
  }
  for (int i = f[x].size() - 1; i; i--) {
    fx = erfen(tot2[f[x][i]], id[x]);
    if ((fx ^ tot1[f[x][i]].size()) && tot2[f[x][i]][fx].first == id[y]) {
      tot2[f[x][i]][fx - 1].second = tot2[f[x][i]][fx].second - d[x][i - 1];
    } else {
      fx--;
      tot2[f[x][i]][fx].first++;
    }
  }
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) c[i] = read(), id[c[i]] = i;
  for (int i = 1; i < n; i++) {
    int x = read(), y = read(), z = read();
    add(x, y, z);
    add(y, x, z);
  }
  maxsz[0] = 1e9 + 10;
  findrt(1, 0, n);
  rt = now;
  dfs(now);
  while (m--) {
    int mode, x, y, z;
    scanf("%d", &mode);
    if (mode == 1) {
      scanf("%d%d%d", &x, &y, &z);
      x ^= ans;
      y ^= ans;
      z ^= ans;
      ans = ask(z, x, y);
      printf("%lld\n", ans);
      ans &= (1 << 30) - 1;
    } else {
      scanf("%d", &x);
      x ^= ans;
      update(c[x], c[x + 1]);
      id[c[x]]++;
      id[c[x + 1]]--;
      swap(c[x], c[x + 1]);
    }
  }
  return 0;
}

```