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 = .2e6 + 5;
const int X = 20;
vector<pair<int, pair<long long, long long> > > S[N];
vector<pair<long long, long long> > CS[N];
set<pair<long long, long long> > adj[N];
int nn;
int subsize[N];
int dpar[N];
int dep[N];
long long dist[X][N];
void sub_dfs(int v, int p) {
  nn++;
  subsize[v] = 1;
  for (auto it = adj[v].begin(); it != adj[v].end(); it++) {
    if (it->first == p) continue;
    sub_dfs(it->first, v);
    subsize[v] += subsize[it->first];
  }
}
int find_centroid(int v, int p) {
  for (auto it = adj[v].begin(); it != adj[v].end(); it++) {
    if (it->first == p) continue;
    if (subsize[it->first] > nn / 2) return find_centroid(it->first, v);
  }
  return v;
}
void initialiseDists(int v, int p, long long dist[]) {
  for (auto &it : adj[v]) {
    if (it.first == p) continue;
    dist[it.first] = dist[v] + it.second;
    initialiseDists(it.first, v, dist);
  }
}
void decompose(int v, int p) {
  nn = 0;
  sub_dfs(v, 0);
  int c = find_centroid(v, 0);
  dpar[c] = p;
  dep[c] = dep[p] + 1;
  initialiseDists(c, 0, dist[dep[c]]);
  for (auto it = adj[c].begin(); it != adj[c].end(); it++) {
    adj[it->first].erase(make_pair(c, it->second));
    decompose(it->first, c);
  }
  adj[c].clear();
}
void addNode(int v, int in) {
  int x = v;
  int d = dep[v];
  while (x) {
    S[x].push_back(pair<int, pair<long long, long long> >(
        in, pair<long long, long long>(dist[d][v], dist[d - 1][v])));
    x = dpar[x];
    d--;
  }
}
void increaseIndex(int v, int in) {
  int x = v;
  int d = dep[v];
  while (x) {
    int p =
        lower_bound(
            S[x].begin(), S[x].end(),
            pair<int, pair<long long, long long> >(
                in, pair<long long, long long>(dist[d][v], dist[d - 1][v]))) -
        S[x].begin();
    S[x][p].first++;
    if (p < (int)S[x].size() - 1 and S[x][p + 1] < S[x][p]) {
      swap(S[x][p], S[x][p + 1]);
      CS[x][p] = pair<long long, long long>(
          CS[x][p + 1].first - S[x][p + 1].second.first,
          CS[x][p + 1].second - S[x][p + 1].second.second);
    }
    x = dpar[x];
    d--;
  }
}
void decreaseIndex(int v, int in) {
  int x = v;
  int d = dep[v];
  while (x) {
    int p =
        lower_bound(
            S[x].begin(), S[x].end(),
            pair<int, pair<long long, long long> >(
                in, pair<long long, long long>(dist[d][v], dist[d - 1][v]))) -
        S[x].begin();
    S[x][p].first--;
    if (p and S[x][p - 1] > S[x][p]) {
      swap(S[x][p], S[x][p - 1]);
      CS[x][p - 1] =
          pair<long long, long long>(CS[x][p].first - S[x][p].second.first,
                                     CS[x][p].second - S[x][p].second.second);
    }
    x = dpar[x];
    d--;
  }
}
long long query(int v, int r) {
  int x = v;
  int d = dep[v];
  long long ans = 0;
  pair<int, pair<long long, long long> > last =
      pair<int, pair<long long, long long> >(0,
                                             pair<long long, long long>(0, 0));
  while (x) {
    int p = upper_bound(S[x].begin(), S[x].end(),
                        pair<int, pair<long long, long long> >(
                            r + 1, pair<long long, long long>(-1, -1))) -
            S[x].begin() - 1;
    pair<int, pair<long long, long long> > ret =
        pair<int, pair<long long, long long> >(
            0, pair<long long, long long>(0, 0));
    if (p >= 0) ret = pair<int, pair<long long, long long> >(p + 1, CS[x][p]);
    ans += ret.second.first - last.second.second +
           dist[d][v] * (ret.first - last.first);
    last = ret;
    x = dpar[x];
    d--;
  }
  return ans;
}
int A[N], invA[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> A[i];
    invA[A[i]] = i;
  }
  for (int i = 1; i < n; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].insert(make_pair(b, c));
    adj[b].insert(make_pair(a, c));
  }
  decompose(1, 0);
  for (int i = 1; i <= n; i++) {
    addNode(i, invA[i]);
  }
  for (int i = 1; i <= n; i++) {
    sort(S[i].begin(), S[i].end());
    CS[i].resize(S[i].size());
    CS[i][0] = S[i][0].second;
    for (int j = 1; j < (int)S[i].size(); j++) {
      CS[i][j] = pair<long long, long long>(
          CS[i][j - 1].first + S[i][j].second.first,
          CS[i][j - 1].second + S[i][j].second.second);
    }
  }
  long long ans = 0;
  for (int i = 1; i <= q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int a, b, c;
      cin >> a >> b >> c;
      int l = ans ^ a, r = ans ^ b, v = ans ^ c;
      ans = query(v, r) - query(v, l - 1);
      cout << ans << "\n";
    } else {
      int a;
      cin >> a;
      int x = ans ^ a;
      increaseIndex(A[x], x);
      decreaseIndex(A[x + 1], x + 1);
      swap(A[x], A[x + 1]);
      invA[A[x]] = x, invA[A[x + 1]] = x + 1;
    }
    ans &= (1 << 30) - 1;
  }
  return 0;
}