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;
const int N = 200500;
const int LGN = 19;
int n;
struct vert {
  int c = -1;
  long long d = -1;
};
vector<vert> info;
struct layer {
  std::vector<pair<int, long long>> srt;
  std::vector<int> x;
  std::vector<long long> S;
  int depth = 0;
} L[N];
bool rem[N];
int sz[N];
vector<pair<int, int>> E[N];
int centroid(int x, int all_sz, int p = -1) {
  sz[x] = 1;
  int glob_res = -1;
  for (auto pr : E[x]) {
    int y = pr.first;
    if (rem[y] || p == y) continue;
    int res = centroid(y, all_sz, x);
    if (res != -1) {
      glob_res = res;
    }
    sz[x] += sz[y];
  }
  if (glob_res != -1) return glob_res;
  bool is_centroid = all_sz - sz[x] <= all_sz / 2;
  for (auto pr : E[x]) {
    int y = pr.first;
    if (rem[y] || p == y) continue;
    is_centroid &= sz[y] <= all_sz / 2;
  }
  if (is_centroid) return x;
  return -1;
}
int A[N], IA[N];
void DFS(int x, int depth, int c, int p = -1, long long d = 0) {
  info[x * LGN + depth].c = c;
  info[x * LGN + depth].d = d;
  sz[x] = 1;
  L[c].srt.emplace_back(IA[x],
                        d - ((depth > 0) ? info[x * LGN + depth - 1].d : 0));
  for (auto pr : E[x]) {
    int y = pr.first;
    int w = pr.second;
    if (y == p || rem[y]) continue;
    DFS(y, depth, c, x, d + w);
    sz[x] += sz[y];
  }
}
void build_layer(int x, int all_sz, int depth) {
  assert(!rem[x]);
  int c = centroid(x, all_sz);
  assert(c != -1);
  x = c;
  L[x].depth = depth;
  for (auto pr : E[x]) {
    int y = pr.first;
    int w = pr.second;
    if (rem[y]) continue;
    DFS(y, depth, x, x, w);
  }
  L[x].srt.emplace_back(IA[x],
                        0 - ((depth > 0) ? info[x * LGN + depth - 1].d : 0));
  info[x * LGN + depth].c = x;
  info[x * LGN + depth].d = 0;
  rem[x] = true;
  for (auto pr : E[x]) {
    int y = pr.first;
    if (!rem[y]) {
      build_layer(y, sz[y], depth + 1);
    }
  }
}
long long query(int v, int l, int r) {
  assert(1 <= l && l <= r && r <= n);
  assert(1 <= v && v <= n);
  long long sum = 0;
  long long c1 = 0, c2 = 0;
  for (int depth = 0;; depth++) {
    int c = info[v * LGN + depth].c;
    long long d = info[v * LGN + depth].d;
    if (c == -1) break;
    long long sumd = 0;
    int i1 = lower_bound(L[c].x.begin(), L[c].x.end(), l) - L[c].x.begin() - 1;
    int i2 = upper_bound(L[c].x.begin(), L[c].x.end(), r) - L[c].x.begin() - 1;
    if (i1 >= 0) {
      sumd -= L[c].S[i1];
    }
    if (i2 >= 0) {
      sumd += L[c].S[i2];
    }
    sum += sumd + (d + c2) * (i2 - i1);
    c1 = -1, c2 = -d;
  }
  return sum;
}
void change(int x1, int x2, int v1, int v2) {
  assert(v1 != v2);
  assert(x1 + 1 == x2);
  int depth;
  for (depth = 0;; depth++) {
    if (info[v1 * LGN + depth].c != info[v2 * LGN + depth].c) break;
    int c = info[v1 * LGN + depth].c;
    int i1 = lower_bound(L[c].x.begin(), L[c].x.end(), x1) - L[c].x.begin();
    assert(i1 + 1 <= L[c].S.size() && L[c].x[i1] == x1);
    int i2 = i1 + 1;
    assert(i2 + 1 <= L[c].S.size() && L[c].x[i2] == x2);
    auto pi = i1 - 1;
    long long ps = 0;
    if (pi >= 0) {
      ps = L[c].S[pi];
    }
    long long s1 = L[c].S[i1] - ps;
    long long s2 = L[c].S[i2] - L[c].S[i1];
    L[c].S[i1] = ps + s2;
  }
  for (int depth1 = depth;; depth1++) {
    int c = info[v1 * LGN + depth1].c;
    if (c == -1) break;
    int i1 = lower_bound(L[c].x.begin(), L[c].x.end(), x1) - L[c].x.begin();
    assert(i1 < (int)L[c].x.size() && L[c].x[i1] == x1);
    L[c].x[i1]++;
  }
  for (int depth2 = depth;; depth2++) {
    int c = info[v2 * LGN + depth2].c;
    if (c == -1) break;
    int i2 = lower_bound(L[c].x.begin(), L[c].x.end(), x2) - L[c].x.begin();
    assert(i2 < (int)L[c].x.size() && L[c].x[i2] == x2);
    L[c].x[i2]--;
  }
  A[x1] = v2, A[x2] = v1, IA[v1] = x2, IA[v2] = x1;
}
const bool bitch_input = true;
int main() {
  info.resize(N * LGN);
  int q;
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &A[i]);
    IA[A[i]] = i;
  }
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    E[u].emplace_back(v, w);
    E[v].emplace_back(u, w);
  }
  build_layer(1, n, 0);
  for (int i = 1; i <= n; i++) assert(rem[i]);
  long long pans = 0;
  const int BIT = (1 << 30) - 1;
  for (int i = 1; i <= n; i++) {
    sort(L[i].srt.begin(), L[i].srt.end());
    long long s = 0;
    int cnt = 0;
    for (int j = 0; j < (int)L[i].srt.size(); j++) {
      L[i].x.emplace_back(L[i].srt[j].first);
      s += L[i].srt[j].second;
      cnt++;
      L[i].S.emplace_back(s);
    }
    L[i].srt.clear();
  }
  for (int i = 0; i < q; i++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int a, b, c;
      scanf("%d %d %d", &a, &b, &c);
      int l, r, v;
      if (bitch_input) {
        l = (pans & BIT) ^ a;
        r = (pans & BIT) ^ b;
        v = (pans & BIT) ^ c;
      } else {
        l = a, r = b, v = c;
      }
      long long ans = query(v, l, r);
      printf("%lld\n", ans);
      pans = ans;
    } else {
      int a;
      scanf("%d", &a);
      int x;
      if (bitch_input) {
        x = (pans & BIT) ^ a;
      } else {
        x = a;
      }
      change(x, x + 1, A[x], A[x + 1]);
    }
  }
}