#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
constexpr long long mod = 1000000007;
const long long INF = mod * mod;
const double eps = 1e-8;
const double pi = acosl(-1.0);
long long mod_pow(long long x, long long n, long long m = mod) {
  if (n < 0) {
    long long res = mod_pow(x, -n, m);
    return mod_pow(res, m - 2, m);
  }
  if (abs(x) >= m) x %= m;
  if (x < 0) x += m;
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % m;
    x = x * x % m;
    n >>= 1;
  }
  return res;
}
struct modint {
  long long n;
  modint() : n(0) { ; }
  modint(long long m) : n(m) {
    if (n >= mod)
      n %= mod;
    else if (n < 0)
      n = (n % mod + mod) % mod;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod) a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0) a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((long long)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, long long n) {
  if (n == 0) return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}
long long inv(long long a, long long p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}
const int max_n = 1 << 1;
modint fact[max_n], factinv[max_n];
void init_f() {
  fact[0] = modint(1);
  for (int i = 0; i < max_n - 1; i++) {
    fact[i + 1] = fact[i] * modint(i + 1);
  }
  factinv[max_n - 1] = modint(1) / fact[max_n - 1];
  for (int i = max_n - 2; i >= 0; i--) {
    factinv[i] = factinv[i + 1] * modint(i + 1);
  }
}
modint comb(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[a - b];
}
vector<int> trans;
struct edge {
  int to, cost;
};
struct Centroid_Decomposition {
 private:
  int n;
  vector<vector<edge>> G;
  vector<vector<int>> fG;
  int root;
  vector<int> par, parid;
  vector<vector<vector<long long>>> dists;
  vector<vector<vector<int>>> ids;
  vector<vector<long long>> pdist;
  vector<vector<int>> pid;
  vector<vector<pair<long long, long long>>> pars;
  vector<long long> dep;

 public:
  Centroid_Decomposition(int n_) {
    n = n_;
    G.resize(n);
    par.resize(n);
    parid.resize(n);
    pars.resize(n);
    fG.resize(n);
    root = -1;
    dists.resize(n);
    ids.resize(n);
    pdist.resize(n);
    pid.resize(n);
  }
  void add_edge(int a, int b, int c) {
    G[a].push_back({b, c});
    G[b].push_back({a, c});
  }
  void complete() {
    vector<int> exi(n, 0);
    vector<int> ori(n);
    for (int i = 0; i < n; i++) ori[i] = i;
    int tmp = 0;
    function<int(int, int, int&, int&)> szdfs = [&](int id, int fr, int& g,
                                                    int& sz) -> int {
      int res = 1;
      int ma = 0;
      for (edge e : G[id]) {
        if (tmp != exi[e.to]) continue;
        if (e.to == fr) continue;
        int nex = szdfs(e.to, id, g, sz);
        ma = max(ma, nex);
        res += nex;
      }
      if (ma <= sz / 2 && sz - res <= sz / 2) g = id;
      return res;
    };
    function<int(vector<int>)> cdfs = [&](vector<int> v) -> int {
      tmp++;
      if (v.empty()) return 0;
      for (int id : v) {
        exi[id]++;
      }
      int g;
      int sz = v.size();
      szdfs(v[0], -1, g, sz);
      pdist[g].push_back(0);
      pid[g].push_back(trans[g]);
      pars[g].push_back({g, 0});
      for (edge e : G[g]) {
        if (!exi[e.to]) continue;
        if (exi[e.to] != tmp) continue;
        int t = dists[g].size();
        dists[g].push_back({});
        ids[g].push_back({});
        queue<pair<pair<int, int>, long long>> vs;
        vs.push({{e.to, g}, e.cost});
        vector<int> nex;
        while (!vs.empty()) {
          pair<pair<int, int>, long long> p = vs.front();
          vs.pop();
          int v = p.first.first, fr = p.first.second;
          nex.push_back(v);
          pdist[g].push_back(p.second);
          pid[g].push_back(trans[v]);
          dists[g][t].push_back(p.second);
          ids[g][t].push_back(trans[v]);
          pars[v].push_back({g, p.second});
          for (edge e : G[v]) {
            if (e.to == fr) continue;
            if (tmp != exi[e.to]) continue;
            vs.push({{e.to, v}, p.second + e.cost});
          }
        }
        int ng = cdfs(nex);
        fG[g].push_back(ng);
        par[ng] = g;
        parid[ng] = t;
      }
      for (int id : v) {
        exi[id]--;
      }
      tmp--;
      return g;
    };
    root = cdfs(ori);
    par[root] = -1;
    auto yaru = [&](vector<int>& id, vector<long long>& dist) {
      vector<pair<long long, long long>> cop(id.size());
      for (int j = 0; j < id.size(); j++) {
        cop[j] = {id[j], dist[j]};
      }
      sort((cop).begin(), (cop).end());
      long long sum = 0;
      for (int j = 0; j < id.size(); j++) {
        dist[j] = sum;
        id[j] = cop[j].first;
        sum += cop[j].second;
      }
      dist.push_back(sum);
    };
    for (int i = 0; i < n; i++) {
      yaru(pid[i], pdist[i]);
      for (int j = 0; j < dists[i].size(); j++) {
        yaru(ids[i][j], dists[i][j]);
      }
    }
    dep.resize(n);
    dep[0] = 0;
    function<void(int, int)> depdfs = [&](int id, int fr) {
      for (edge e : G[id])
        if (e.to != fr) {
          dep[e.to] = dep[id] + e.cost;
          depdfs(e.to, id);
        }
    };
    depdfs(0, -1);
  }
  void chupd(vector<int>& v, vector<long long>& dist, int loc) {
    if (loc > 0 && v[loc - 1] >= v[loc]) {
      swap(v[loc - 1], v[loc]);
      long long d2 = dist[loc + 1] - dist[loc];
      dist[loc] = dist[loc - 1] + d2;
    } else if (loc + 1 < v.size() && v[loc] >= v[loc + 1]) {
      swap(v[loc], v[loc + 1]);
      long long d2 = dist[loc + 2] - dist[loc + 1];
      dist[loc + 1] = dist[loc] + d2;
    }
  }
  void upd(int c, bool isadd) {
    int loc = trans[c];
    int coef = -1;
    if (isadd) coef = 1;
    int g = c;
    int id;
    while (g >= 0) {
      int t =
          lower_bound((pid[g]).begin(), (pid[g]).end(), loc) - pid[g].begin();
      pid[g][t] += coef;
      if (isadd) chupd(pid[g], pdist[g], t);
      if (g == c) {
      } else {
        t = lower_bound((ids[g][id]).begin(), (ids[g][id]).end(), loc) -
            ids[g][id].begin();
        ids[g][id][t] += coef;
        if (isadd) chupd(ids[g][id], dists[g][id], t);
      }
      id = parid[g];
      g = par[g];
    }
  }
  long long getsum(int c, int l, int r) {
    long long res = 0;
    int g = c;
    int id;
    int tmp = pars[c].size() - 1;
    while (g >= 0) {
      if (g == c) {
        int t =
            lower_bound((pid[g]).begin(), (pid[g]).end(), r) - pid[g].begin();
        res += pdist[g][t];
        t = lower_bound((pid[g]).begin(), (pid[g]).end(), l) - pid[g].begin();
        res -= pdist[g][t];
      } else {
        long long dec = pars[c][tmp].second;
        int t =
            lower_bound((pid[g]).begin(), (pid[g]).end(), r) - pid[g].begin();
        res += pdist[g][t] + dec * t;
        t = lower_bound((ids[g][id]).begin(), (ids[g][id]).end(), r) -
            ids[g][id].begin();
        res -= dists[g][id][t] + dec * t;
        t = lower_bound((pid[g]).begin(), (pid[g]).end(), l) - pid[g].begin();
        res -= pdist[g][t] + dec * t;
        t = lower_bound((ids[g][id]).begin(), (ids[g][id]).end(), l) -
            ids[g][id].begin();
        res += dists[g][id][t] + dec * t;
      }
      id = parid[g];
      g = par[g];
      tmp--;
    }
    return res;
  }
};
void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  trans.resize(n);
  for (int i = 0; i < n; i++) trans[a[i]] = i;
  Centroid_Decomposition cd(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    cd.add_edge(a, b, c);
  }
  cd.complete();
  long long las = 0;
  for (int i = 0; i < q; i++) {
    las %= (1 << 30);
    int typ;
    cin >> typ;
    if (typ == 1) {
      int l, r, v;
      cin >> l >> r >> v;
      l ^= las;
      r ^= las;
      v ^= las;
      l--;
      r--;
      v--;
      long long ans = cd.getsum(v, l, r + 1);
      cout << ans << "\n";
      las = ans;
    } else {
      int x;
      cin >> x;
      x ^= las;
      x--;
      cd.upd(a[x], true);
      cd.upd(a[x + 1], false);
      trans[a[x]]++;
      trans[a[x + 1]]--;
      swap(a[x], a[x + 1]);
    }
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

### Prompt

Please create a solution in cpp to the following 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

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
constexpr long long mod = 1000000007;
const long long INF = mod * mod;
const double eps = 1e-8;
const double pi = acosl(-1.0);
long long mod_pow(long long x, long long n, long long m = mod) {
  if (n < 0) {
    long long res = mod_pow(x, -n, m);
    return mod_pow(res, m - 2, m);
  }
  if (abs(x) >= m) x %= m;
  if (x < 0) x += m;
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % m;
    x = x * x % m;
    n >>= 1;
  }
  return res;
}
struct modint {
  long long n;
  modint() : n(0) { ; }
  modint(long long m) : n(m) {
    if (n >= mod)
      n %= mod;
    else if (n < 0)
      n = (n % mod + mod) % mod;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod) a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0) a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((long long)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, long long n) {
  if (n == 0) return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}
long long inv(long long a, long long p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}
const int max_n = 1 << 1;
modint fact[max_n], factinv[max_n];
void init_f() {
  fact[0] = modint(1);
  for (int i = 0; i < max_n - 1; i++) {
    fact[i + 1] = fact[i] * modint(i + 1);
  }
  factinv[max_n - 1] = modint(1) / fact[max_n - 1];
  for (int i = max_n - 2; i >= 0; i--) {
    factinv[i] = factinv[i + 1] * modint(i + 1);
  }
}
modint comb(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[a - b];
}
vector<int> trans;
struct edge {
  int to, cost;
};
struct Centroid_Decomposition {
 private:
  int n;
  vector<vector<edge>> G;
  vector<vector<int>> fG;
  int root;
  vector<int> par, parid;
  vector<vector<vector<long long>>> dists;
  vector<vector<vector<int>>> ids;
  vector<vector<long long>> pdist;
  vector<vector<int>> pid;
  vector<vector<pair<long long, long long>>> pars;
  vector<long long> dep;

 public:
  Centroid_Decomposition(int n_) {
    n = n_;
    G.resize(n);
    par.resize(n);
    parid.resize(n);
    pars.resize(n);
    fG.resize(n);
    root = -1;
    dists.resize(n);
    ids.resize(n);
    pdist.resize(n);
    pid.resize(n);
  }
  void add_edge(int a, int b, int c) {
    G[a].push_back({b, c});
    G[b].push_back({a, c});
  }
  void complete() {
    vector<int> exi(n, 0);
    vector<int> ori(n);
    for (int i = 0; i < n; i++) ori[i] = i;
    int tmp = 0;
    function<int(int, int, int&, int&)> szdfs = [&](int id, int fr, int& g,
                                                    int& sz) -> int {
      int res = 1;
      int ma = 0;
      for (edge e : G[id]) {
        if (tmp != exi[e.to]) continue;
        if (e.to == fr) continue;
        int nex = szdfs(e.to, id, g, sz);
        ma = max(ma, nex);
        res += nex;
      }
      if (ma <= sz / 2 && sz - res <= sz / 2) g = id;
      return res;
    };
    function<int(vector<int>)> cdfs = [&](vector<int> v) -> int {
      tmp++;
      if (v.empty()) return 0;
      for (int id : v) {
        exi[id]++;
      }
      int g;
      int sz = v.size();
      szdfs(v[0], -1, g, sz);
      pdist[g].push_back(0);
      pid[g].push_back(trans[g]);
      pars[g].push_back({g, 0});
      for (edge e : G[g]) {
        if (!exi[e.to]) continue;
        if (exi[e.to] != tmp) continue;
        int t = dists[g].size();
        dists[g].push_back({});
        ids[g].push_back({});
        queue<pair<pair<int, int>, long long>> vs;
        vs.push({{e.to, g}, e.cost});
        vector<int> nex;
        while (!vs.empty()) {
          pair<pair<int, int>, long long> p = vs.front();
          vs.pop();
          int v = p.first.first, fr = p.first.second;
          nex.push_back(v);
          pdist[g].push_back(p.second);
          pid[g].push_back(trans[v]);
          dists[g][t].push_back(p.second);
          ids[g][t].push_back(trans[v]);
          pars[v].push_back({g, p.second});
          for (edge e : G[v]) {
            if (e.to == fr) continue;
            if (tmp != exi[e.to]) continue;
            vs.push({{e.to, v}, p.second + e.cost});
          }
        }
        int ng = cdfs(nex);
        fG[g].push_back(ng);
        par[ng] = g;
        parid[ng] = t;
      }
      for (int id : v) {
        exi[id]--;
      }
      tmp--;
      return g;
    };
    root = cdfs(ori);
    par[root] = -1;
    auto yaru = [&](vector<int>& id, vector<long long>& dist) {
      vector<pair<long long, long long>> cop(id.size());
      for (int j = 0; j < id.size(); j++) {
        cop[j] = {id[j], dist[j]};
      }
      sort((cop).begin(), (cop).end());
      long long sum = 0;
      for (int j = 0; j < id.size(); j++) {
        dist[j] = sum;
        id[j] = cop[j].first;
        sum += cop[j].second;
      }
      dist.push_back(sum);
    };
    for (int i = 0; i < n; i++) {
      yaru(pid[i], pdist[i]);
      for (int j = 0; j < dists[i].size(); j++) {
        yaru(ids[i][j], dists[i][j]);
      }
    }
    dep.resize(n);
    dep[0] = 0;
    function<void(int, int)> depdfs = [&](int id, int fr) {
      for (edge e : G[id])
        if (e.to != fr) {
          dep[e.to] = dep[id] + e.cost;
          depdfs(e.to, id);
        }
    };
    depdfs(0, -1);
  }
  void chupd(vector<int>& v, vector<long long>& dist, int loc) {
    if (loc > 0 && v[loc - 1] >= v[loc]) {
      swap(v[loc - 1], v[loc]);
      long long d2 = dist[loc + 1] - dist[loc];
      dist[loc] = dist[loc - 1] + d2;
    } else if (loc + 1 < v.size() && v[loc] >= v[loc + 1]) {
      swap(v[loc], v[loc + 1]);
      long long d2 = dist[loc + 2] - dist[loc + 1];
      dist[loc + 1] = dist[loc] + d2;
    }
  }
  void upd(int c, bool isadd) {
    int loc = trans[c];
    int coef = -1;
    if (isadd) coef = 1;
    int g = c;
    int id;
    while (g >= 0) {
      int t =
          lower_bound((pid[g]).begin(), (pid[g]).end(), loc) - pid[g].begin();
      pid[g][t] += coef;
      if (isadd) chupd(pid[g], pdist[g], t);
      if (g == c) {
      } else {
        t = lower_bound((ids[g][id]).begin(), (ids[g][id]).end(), loc) -
            ids[g][id].begin();
        ids[g][id][t] += coef;
        if (isadd) chupd(ids[g][id], dists[g][id], t);
      }
      id = parid[g];
      g = par[g];
    }
  }
  long long getsum(int c, int l, int r) {
    long long res = 0;
    int g = c;
    int id;
    int tmp = pars[c].size() - 1;
    while (g >= 0) {
      if (g == c) {
        int t =
            lower_bound((pid[g]).begin(), (pid[g]).end(), r) - pid[g].begin();
        res += pdist[g][t];
        t = lower_bound((pid[g]).begin(), (pid[g]).end(), l) - pid[g].begin();
        res -= pdist[g][t];
      } else {
        long long dec = pars[c][tmp].second;
        int t =
            lower_bound((pid[g]).begin(), (pid[g]).end(), r) - pid[g].begin();
        res += pdist[g][t] + dec * t;
        t = lower_bound((ids[g][id]).begin(), (ids[g][id]).end(), r) -
            ids[g][id].begin();
        res -= dists[g][id][t] + dec * t;
        t = lower_bound((pid[g]).begin(), (pid[g]).end(), l) - pid[g].begin();
        res -= pdist[g][t] + dec * t;
        t = lower_bound((ids[g][id]).begin(), (ids[g][id]).end(), l) -
            ids[g][id].begin();
        res += dists[g][id][t] + dec * t;
      }
      id = parid[g];
      g = par[g];
      tmp--;
    }
    return res;
  }
};
void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  trans.resize(n);
  for (int i = 0; i < n; i++) trans[a[i]] = i;
  Centroid_Decomposition cd(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    cd.add_edge(a, b, c);
  }
  cd.complete();
  long long las = 0;
  for (int i = 0; i < q; i++) {
    las %= (1 << 30);
    int typ;
    cin >> typ;
    if (typ == 1) {
      int l, r, v;
      cin >> l >> r >> v;
      l ^= las;
      r ^= las;
      v ^= las;
      l--;
      r--;
      v--;
      long long ans = cd.getsum(v, l, r + 1);
      cout << ans << "\n";
      las = ans;
    } else {
      int x;
      cin >> x;
      x ^= las;
      x--;
      cd.upd(a[x], true);
      cd.upd(a[x + 1], false);
      trans[a[x]]++;
      trans[a[x + 1]]--;
      swap(a[x], a[x + 1]);
    }
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

```