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>
using namespace std;
int sz[200100];
vector<int> g[200100], w[200100];
int loc[200100][20], dep[200100], tloc[20], td;
long long len[200100][20];
bool del[200100];
void build(int u, int p, int ly, long long d) {
  sz[u] = 1;
  len[u][ly] = d;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (v == p || del[v]) continue;
    build(v, u, ly, d + w[u][i]);
    sz[u] += sz[v];
  }
}
void decom(int u) {
  build(u, 0, td, 0);
  int tsz = sz[u], p = -1;
  bool flag = true;
  while (flag) {
    flag = false;
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i];
      if (del[v] || v == p) continue;
      if (sz[v] + sz[v] > tsz) {
        p = u;
        u = v;
        flag = true;
        break;
      }
    }
  }
  build(u, 0, td, 0);
  tloc[td++] = u;
  dep[u] = td;
  for (int i = 0; i < td; i++) {
    loc[u][i] = tloc[i];
  }
  del[u] = true;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (del[v]) continue;
    decom(v);
  }
  td--;
}
int a[200100];
vector<long long> sum[200100];
vector<int> ts[200100];
int pos[200100][20];
int main() {
  int n, q, u, v, x, t, l, r;
  long long ans = 0, msk = (1LL << 30) - 1;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i < n; i++) {
    scanf("%d%d%d", &u, &v, &x);
    g[u].push_back(v);
    g[v].push_back(u);
    w[u].push_back(x);
    w[v].push_back(x);
  }
  decom(1);
  for (int i = 1; i <= n; i++) {
    sum[i].push_back(0);
    ts[i].push_back(-1);
  }
  for (int i = 0; i < n; i++) {
    u = a[i];
    for (int j = 0; j < dep[u]; j++) {
      sum[loc[u][j]].push_back(sum[loc[u][j]].back() + len[u][j] -
                               (j > 0 ? len[u][j - 1] : 0));
      pos[u][j] = ts[loc[u][j]].size();
      ts[loc[u][j]].push_back(i);
    }
  }
  while (q--) {
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d%d%d", &l, &r, &u);
      l = msk & ans ^ l;
      r = msk & ans ^ r;
      u = msk & ans ^ u;
      l--, r--;
      ans = 0;
      for (int i = 0; i < dep[u]; i++) {
        v = loc[u][i];
        int pr = upper_bound(ts[v].begin(), ts[v].end(), r) - ts[v].begin() - 1,
            pl = lower_bound(ts[v].begin(), ts[v].end(), l) - ts[v].begin() - 1;
        if (pl == pr) break;
        ans += sum[v][pr] - sum[v][pl] +
               (pr - pl) * (len[u][i] - (i > 0 ? len[u][i - 1] : 0));
      }
      printf("%I64d\n", ans);
    } else {
      scanf("%d", &x);
      x = msk & ans ^ x;
      u = a[x], v = a[x - 1];
      for (int i = 0; i < max(dep[u], dep[v]); i++) {
        if (i < min(dep[u], dep[v]) && loc[u][i] == loc[v][i]) {
          sum[loc[u][i]][pos[v][i]] = sum[loc[u][i]][pos[v][i] + 1] -
                                      sum[loc[u][i]][pos[v][i]] +
                                      sum[loc[u][i]][pos[v][i] - 1];
          swap(pos[u][i], pos[v][i]);
        } else {
          if (i < dep[u]) {
            ts[loc[u][i]][pos[u][i]]--;
          }
          if (i < dep[v]) {
            ts[loc[v][i]][pos[v][i]]++;
          }
        }
      }
      swap(a[x], a[x - 1]);
    }
  }
  return 0;
}