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>
int ij[(200000 + 200000) - 1], ww[(200000 + 200000) - 1];
int ae[(200000 + 200000)][3], mm[(200000 + 200000)], n_, m_;
void link(int i, int j, int w, int h) {
  int tmp;
  if (mm[i] < mm[j]) tmp = i, i = j, j = tmp;
  if (mm[i] >= 3) {
    int i_, j_, h_;
    i_ = n_++;
    h_ = ae[i][--mm[i]], j_ = i ^ ij[h_];
    ij[h_] = i_ ^ j_;
    ae[i_][mm[i_]++] = h_;
    h_ = m_++;
    ij[h_] = i_ ^ i, ww[h_] = 0;
    ae[i][mm[i]++] = h_, ae[i_][mm[i_]++] = h_;
    link(i_, j, w, h);
  } else {
    ij[h] = i ^ j, ww[h] = w;
    ae[i][mm[i]++] = h, ae[j][mm[j]++] = h;
  }
}
int sz[(200000 + 200000)], ae_[(200000 + 200000)][3], mm_[(200000 + 200000)],
    cc[(200000 + 200000)][18];
long long dd[(200000 + 200000)][18];
int kk[(200000 + 200000)];
char used[(200000 + 200000)];
int c_;
void dfs(int p, int i, int n, int l, int c, long long d) {
  int g, centroid;
  if (l >= 0) cc[i][l] = c, dd[i][l] = d, kk[i]++;
  centroid = 1;
  sz[i] = 1;
  for (g = 0; g < mm[i]; g++) {
    int h = ae[i][g], j = i ^ ij[h];
    if (j != p && !used[j]) {
      dfs(i, j, n, l, c, d + ww[h]);
      if (sz[j] * 2 > n) centroid = 0;
      sz[i] += sz[j];
    }
  }
  if ((n - sz[i]) * 2 > n) centroid = 0;
  if (centroid) c_ = i;
}
void cd(int i, int n, int l, int c, int w) {
  int g;
  dfs(-1, i, n, l, c, w);
  if (c != -1) ae_[c][mm_[c]++] = c_;
  used[c = c_] = 1;
  for (g = 0; g < mm[c]; g++) {
    int h;
    h = ae[c][g], i = c ^ ij[h];
    if (!used[i]) cd(i, sz[i] < sz[c] ? sz[i] : n - sz[c], l + 1, c, ww[h]);
  }
}
int tt[1 + ((200000 + 200000) * (18 + 1))][3];
long long sum[1 + ((200000 + 200000) * (18 + 1))];
int cnt[1 + ((200000 + 200000) * (18 + 1))];
int copy(int u, int i) {
  static int v;
  int g;
  v++;
  sum[v] = sum[u], cnt[v] = cnt[u];
  for (g = 0; g < mm_[i]; g++) tt[v][g] = tt[u][g];
  return v;
}
int update(int u, int i) {
  int t, u_, l;
  t = u_ = copy(u, kk[i] == 0 ? i : cc[i][0]);
  for (l = 0; l < kk[i]; l++) {
    int j, j_, g;
    j = cc[i][l], j_ = l + 1 == kk[i] ? i : cc[i][l + 1];
    sum[u_] += dd[i][l], cnt[u_]++;
    for (g = 0; g < mm_[j]; g++)
      if (j_ == ae_[j][g]) {
        u_ = tt[u_][g] = copy(u = tt[u][g], j_);
        break;
      }
    sum[u_] -= dd[i][l];
  }
  cnt[u_]++;
  return t;
}
long long query(int u, int i) {
  int l;
  long long ans;
  ans = 0;
  for (l = 0; l < kk[i]; l++) {
    int j, j_, v, g;
    j = cc[i][l], j_ = l + 1 == kk[i] ? i : cc[i][l + 1];
    v = -1;
    for (g = 0; g < mm_[j]; g++)
      if (j_ == ae_[j][g]) {
        v = tt[u][g];
        break;
      }
    if (u) ans += sum[u] + (cnt[u] - cnt[v]) * dd[i][l];
    u = v;
  }
  ans += sum[u];
  return ans;
}
int main() {
  static int pp[200000], uu[200000];
  int n, q, h, i, j, w;
  long long ans;
  scanf("%d%d", &n, &q);
  for (i = 0; i < n; i++) scanf("%d", &pp[i]), pp[i]--;
  for (i = 0; i < n; i++) ae[i][0] = ae[i][1] = ae[i][2] = -1;
  n_ = n, m_ = n - 1;
  for (h = 0; h < n - 1; h++) {
    scanf("%d%d%d", &i, &j, &w), i--, j--;
    link(i, j, w, h);
  }
  cd(0, n_, -1, -1, 0);
  for (i = 0; i < n; i++) uu[i] = update(i == 0 ? 0 : uu[i - 1], pp[i]);
  ans = 0;
  while (q--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int l, r;
      scanf("%d%d%d", &l, &r, &i), l ^= ans % (1 << 30), r ^= ans % (1 << 30),
          i ^= ans % (1 << 30), l--, r--, i--;
      printf("%lld\n",
             (ans = query(uu[r], i) - (l == 0 ? 0 : query(uu[l - 1], i))));
    } else {
      int tmp;
      scanf("%d", &i), i ^= ans % (1 << 30), i--;
      tmp = pp[i], pp[i] = pp[i + 1], pp[i + 1] = tmp;
      uu[i] = update(i == 0 ? 0 : uu[i - 1], pp[i]);
    }
  }
  return 0;
}