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>
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using ld = long double;
const int N = 200000;
int n, q;
int a[N];
vector<pii> g[N];
int in_perm[N];
bool ban[N];
int sizes[N];
void calc_sizes(int v, int p) {
  sizes[v] = 1;
  for (const pii& e : g[v]) {
    if (e.first != p && !ban[e.first]) {
      calc_sizes(e.first, v);
      sizes[v] += sizes[e.first];
    }
  }
}
int get_cent(int v, int p, int n) {
  for (const pii& e : g[v]) {
    if (e.first != p && !ban[e.first] && 2 * sizes[e.first] > n) {
      return get_cent(e.first, v, n);
    }
  }
  return v;
}
const int L = 18;
int pc[N];
int v_lvl[N];
ll dep[L][N];
vi cst[N];
vector<ll> ft[N];
int sec_p[L][N];
vi sec_cst[L][N];
vector<ll> sec_ft[L][N];
void dfs_cst(int v, int p, int where, int lvl, int sec_v) {
  if (v != where) {
    if (sec_v == -1) {
      sec_v = v;
    }
  }
  sec_p[lvl][v] = sec_v;
  cst[where].push_back(v);
  if (sec_v != -1) {
    sec_cst[lvl][sec_v].push_back(v);
  }
  for (const pii& e : g[v]) {
    if (e.first != p && !ban[e.first]) {
      dep[lvl][e.first] = dep[lvl][v] + e.second;
      dfs_cst(e.first, v, where, lvl, sec_v);
    }
  }
}
bool cmp(int u, int v) { return in_perm[u] < in_perm[v]; }
void cent_dec(int v, int p, int lvl) {
  calc_sizes(v, -1);
  v = get_cent(v, -1, sizes[v]);
  ban[v] = true;
  pc[v] = p;
  v_lvl[v] = lvl;
  dep[lvl][v] = 0;
  dfs_cst(v, -1, v, lvl, -1);
  sort((cst[v]).begin(), (cst[v]).end(), cmp);
  ft[v].resize((int)((cst[v]).size()));
  for (int i = 0; i < (int)((cst[v]).size()); i++) {
    int u = cst[v][i];
    ft[v][i] = (i ? ft[v][i - 1] : 0) + dep[lvl][u];
  }
  for (const pii& e : g[v]) {
    if (!ban[e.first]) {
      sort((sec_cst[lvl][e.first]).begin(), (sec_cst[lvl][e.first]).end(), cmp);
      sec_ft[lvl][e.first].resize((int)((sec_cst[lvl][e.first]).size()));
      for (int i = 0; i < (int)((sec_cst[lvl][e.first]).size()); i++) {
        int u = sec_cst[lvl][e.first][i];
        sec_ft[lvl][e.first][i] =
            (i ? sec_ft[lvl][e.first][i - 1] : 0) + dep[lvl][u];
      }
      cent_dec(e.first, v, lvl + 1);
    }
  }
}
int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    --a[i];
    in_perm[a[i]] = i;
  }
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    --u;
    --v;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  cent_dec(0, -1, 0);
  ll ans = 0;
  const int mod = (1 << 30);
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int l, r, v;
      cin >> l >> r >> v;
      l = (ans % mod) ^ l;
      r = (ans % mod) ^ r;
      v = (ans % mod) ^ v;
      --l;
      --r;
      --v;
      ans = 0;
      int c = v;
      while (c != -1) {
        int lvl = v_lvl[c];
        ll dvc = dep[lvl][v];
        int lb = lower_bound((cst[c]).begin(), (cst[c]).end(), a[l], cmp) -
                 cst[c].begin();
        if (lb < (int)((cst[c]).size()) && in_perm[cst[c][lb]] <= r) {
          int rb = upper_bound((cst[c]).begin(), (cst[c]).end(), a[r], cmp) -
                   cst[c].begin() - 1;
          ans += (rb - lb + 1) * dvc + ft[c][rb] - (lb ? ft[c][lb - 1] : 0);
          if (c != v) {
            int sec_v = sec_p[lvl][v];
            int lb = lower_bound((sec_cst[lvl][sec_v]).begin(),
                                 (sec_cst[lvl][sec_v]).end(), a[l], cmp) -
                     sec_cst[lvl][sec_v].begin();
            if (lb < (int)((sec_cst[lvl][sec_v]).size()) &&
                in_perm[sec_cst[lvl][sec_v][lb]] <= r) {
              int rb = upper_bound((sec_cst[lvl][sec_v]).begin(),
                                   (sec_cst[lvl][sec_v]).end(), a[r], cmp) -
                       sec_cst[lvl][sec_v].begin() - 1;
              ans -= (rb - lb + 1) * dvc + sec_ft[lvl][sec_v][rb] -
                     (lb ? sec_ft[lvl][sec_v][lb - 1] : 0);
            }
          }
        }
        c = pc[c];
      }
      cout << ans << '\n';
    } else {
      int i;
      cin >> i;
      i = (ans % mod) ^ i;
      --i;
      int c;
      {
        int c1 = a[i], c2 = a[i + 1];
        while (c1 != c2) {
          if (v_lvl[c1] < v_lvl[c2]) {
            swap(c1, c2);
          }
          c1 = pc[c1];
        }
        c = c1;
      }
      while (c != -1) {
        int j = lower_bound((cst[c]).begin(), (cst[c]).end(), a[i], cmp) -
                cst[c].begin();
        int lvl = v_lvl[c];
        ft[c][j] += dep[lvl][a[i + 1]] - dep[lvl][a[i]];
        swap(cst[c][j], cst[c][j + 1]);
        if (sec_p[lvl][a[i]] == sec_p[lvl][a[i + 1]]) {
          int sec_v = sec_p[lvl][a[i]];
          int j = lower_bound((sec_cst[lvl][sec_v]).begin(),
                              (sec_cst[lvl][sec_v]).end(), a[i], cmp) -
                  sec_cst[lvl][sec_v].begin();
          sec_ft[lvl][sec_v][j] += dep[lvl][a[i + 1]] - dep[lvl][a[i]];
          swap(sec_cst[lvl][sec_v][j], sec_cst[lvl][sec_v][j + 1]);
        }
        c = pc[c];
      }
      swap(a[i], a[i + 1]);
      in_perm[a[i]] = i;
      in_perm[a[i + 1]] = i + 1;
    }
  }
}