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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const int N = 2e5 + 10, logN = 60;
int n;
struct edge {
  int v, w, la;
  inline void set(int _v, int _w, int _la) {
    v = _v;
    w = _w;
    la = _la;
  }
} e0[N << 1], e[N << 2];
int la0[N], la[N << 1], cnt, cnt1;
int rt[N], lson[N * logN], rson[N * logN], ed[N], tot[N * logN];
long long val[N * logN];
inline void add0(int u, int v, long long w) {
  e0[++cnt].set(v, w, la0[u]);
  la0[u] = cnt;
}
inline void add() {
  int a, b;
  long long c;
  scanf("%d%d%lld", &a, &b, &c);
  add0(a, b, c);
  add0(b, a, c);
}
inline void add(int u, int v, long long w) {
  e[++cnt].set(v, w, la[u]);
  la[u] = cnt;
}
inline void add2(int a, int b, long long c) {
  add(a, b, c);
  add(b, a, c);
}
int max(int a, int b) { return a > b ? a : b; }
void dfs0(int u, int l) {
  for (int i = la0[u], x = 0; i; i = e0[i].la)
    if (e0[i].v != l)
      dfs0(e0[i].v, u), x = (x ? add2(++cnt1, x, 0), cnt1 : u),
                        add2(x, e0[i].v, e0[i].w);
}
int q[N << 1], fa[N << 1], siz[N << 1];
long long dis[N << 1];
bool vis[N << 1];
int bfs(int &x) {
  int i, hd, tl;
  for (fa[q[hd = tl = 1] = x] = 0; hd <= tl; hd++)
    for (i = la[q[hd]]; i; i = e[i].la)
      if (!vis[i >> 1] && e[i].v != fa[q[hd]]) fa[q[++tl] = e[i].v] = q[hd];
  for (hd = tl; hd >= 1; hd--)
    for (i = la[q[hd]], siz[q[hd]] = 1; i; i = e[i].la)
      if (!vis[i >> 1] && e[i].v != fa[q[hd]]) siz[q[hd]] += siz[e[i].v];
  int n = tl;
  for (hd = 1; hd <= tl; hd++)
    if ((siz[q[hd]] = max(siz[q[hd]], n - siz[q[hd]])) < siz[x]) x = q[hd];
  return n;
}
void calc(int u, int v) {
  int i, hd, tl, x = la[u];
  while (e[x].v != v) x = e[x].la;
  vis[x >> 1] = true;
  dis[u] = e[x].w;
  dis[v] = 0;
  for (fa[q[hd = tl = 1] = u] = 0; hd <= tl; hd++) {
    if (q[hd] <= n)
      lson[ed[q[hd]]] = ++cnt, val[ed[q[hd]] = cnt] = dis[q[hd]], tot[cnt] = 1;
    for (i = la[q[hd]]; i; i = e[i].la)
      if (!vis[i >> 1] && e[i].v != fa[q[hd]])
        fa[q[++tl] = e[i].v] = q[hd], dis[e[i].v] = dis[q[hd]] + e[i].w;
  }
  for (fa[q[hd = tl = 1] = v] = 0; hd <= tl; hd++) {
    if (q[hd] <= n)
      rson[ed[q[hd]]] = ++cnt, val[ed[q[hd]] = cnt] = dis[q[hd]], tot[cnt] = 1;
    for (i = la[q[hd]]; i; i = e[i].la)
      if (!vis[i >> 1] && e[i].v != fa[q[hd]])
        fa[q[++tl] = e[i].v] = q[hd], dis[e[i].v] = dis[q[hd]] + e[i].w;
  }
}
void dfs(int x) {
  if (bfs(x) == 1) return;
  int y = fa[x];
  calc(x, y);
  dfs(x);
  dfs(y);
}
void update(int &rt, int ro, int rr) {
  if (!rr) {
    rt = ro;
    return;
  }
  rt = ++cnt;
  val[rt] = val[ro] + val[rr];
  tot[rt] = tot[ro] + tot[rr];
  update(lson[rt], lson[ro], lson[rr]);
  update(rson[rt], rson[ro], rson[rr]);
}
long long query(int rt, int ro, int rr) {
  if (!rr) return 0;
  return query(lson[rt], lson[ro], lson[rr]) +
         query(rson[rt], rson[ro], rson[rr]) +
         (rson[rr] ? val[lson[rt]] - val[lson[ro]] +
                         val[rson[rr]] * (tot[lson[rt]] - tot[lson[ro]])
                   : val[rson[rt]] - val[rson[ro]] +
                         val[lson[rr]] * (tot[rson[rt]] - tot[rson[ro]]));
}
int a[N];
long long lastans;
int main() {
  int i, op, q, x, y, z;
  scanf("%d%d", &n, &q);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (i = 1; i < n; i++) add();
  cnt1 = n;
  cnt = 1;
  dfs0(1, 0);
  cnt = n;
  cnt1 = 0;
  for (i = 1; i <= n; i++) ed[i] = i;
  dfs(1);
  for (i = 1; i <= n; i++) update(rt[i], rt[i - 1], a[i]);
  while (q--) {
    scanf("%d", &op);
    if (op == 1)
      scanf("%d%d%d", &x, &y, &z), x ^= lastans, y ^= lastans, z ^= lastans,
          printf("%lld\n", lastans = query(rt[y], rt[x - 1], z)),
          lastans &= (1 << 30) - 1;
    else
      scanf("%d", &x), x ^= lastans, a[x] ^= a[x + 1] ^= a[x] ^= a[x + 1],
          update(rt[x], rt[x - 1], a[x]);
  }
  return 0;
}