#include <bits/stdc++.h>
using namespace std;
const int N = 5 + 2e5;
template <class T>
void chmax(T& x, T y) {
  y > x ? x = y : T();
}
namespace IO {
const int sz = 1 << 20;
char a[sz + 5], b[sz + 5], *p1 = a, *p2 = a, *t = b, p[105];
inline char gc() {
  return getchar();
  return p1 == p2
             ? (p2 = (p1 = a) + fread(a, 1, sz, stdin), p1 == p2 ? EOF : *p1++)
             : *p1++;
}
template <class T>
void gi(T& x) {
  x = 0;
  char c = gc();
  for (; c < '0' || c > '9'; c = gc())
    ;
  for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
}
inline void flush() { fwrite(b, 1, t - b, stdout), t = b; }
inline void pc(char x) {
  *t++ = x;
  if (t - b == sz) flush();
}
template <class T>
void pi(T x, char c = '\n') {
  if (x < 0) pc('-'), x = -x;
  if (x == 0) pc('0');
  int t = 0;
  for (; x; x /= 10) p[++t] = x % 10 + '0';
  for (; t; --t) pc(p[t]);
  pc(c);
}
struct F {
  ~F() { flush(); }
} f;
}  // namespace IO
using IO::gi;
using IO::pi;
struct S {
  vector<pair<int, long long> > a;
  vector<long long> s;
  void init(vector<pair<int, long long> > _a) {
    a = _a;
    sort(a.begin(), a.end());
    s.resize(a.size());
    s[0] = a[0].second;
    for (int i = 1; i < a.size(); ++i) s[i] = s[i - 1] + a[i].second;
  }
  inline int search(int x) {
    int p = upper_bound(a.begin(), a.end(), make_pair(x, (long long)1e18)) -
            a.begin();
    return p - 1;
  }
  inline pair<long long, int> query(int x) {
    int p = search(x);
    if (p == -1)
      return make_pair(0ll, 0);
    else
      return make_pair(s[p], p + 1);
  }
  inline pair<long long, int> query(int l, int r) {
    pair<long long, int> a = query(r), b = query(l - 1);
    return make_pair(a.first - b.first, a.second - b.second);
  }
  inline void change(int x) {
    int p = search(x), p1;
    p1 = min(p + 1, (int)a.size() - 1);
    if (p == -1 || a[p].first != x) p = -1;
    if (p1 == -1 || a[p1].first != x + 1) p1 = -1;
    if (p != -1) a[p].first++;
    if (p1 != -1) a[p1].first--;
    if (p != -1 && p1 != -1) {
      s[p] += a[p1].second - a[p].second;
      swap(a[p], a[p1]);
    }
  }
};
struct Graph {
  struct Edge {
    int to, nxt, k;
    bool mark;
  } edge[N * 2];
  int head[N], top;
  Graph() { memset(head, -1, sizeof(head)), top = -1; }
  inline void add(int x, int y, int k) {
    edge[++top] = (Edge){y, head[x], k, false};
    head[x] = top;
  }
  inline void add2(int x, int y, int k) { add(x, y, k), add(y, x, k); }
} G;
namespace T {
int dfn[N], dep[N], ti = 0;
long long s[N];
inline int merge(int x, int y) { return dep[x] < dep[y] ? x : y; }
struct ST {
  int st[23][N + N], p[N + N];
  int& operator[](int x) { return st[0][x]; }
  void build(int n) {
    for (int l = 1; 1 << l <= n; ++l)
      for (int i = 1; i + (1 << l) - 1 <= n; ++i)
        st[l][i] = T::merge(st[l - 1][i], st[l - 1][i + (1 << l - 1)]);
    p[1] = 0;
    for (int i = 2; i <= n; ++i) p[i] = p[i >> 1] + 1;
  }
  int query(int x, int y) {
    int l = p[y - x + 1];
    return T::merge(st[l][x], st[l][y - (1 << l) + 1]);
  }
} st;
void dfs(int x, int pre) {
  st[dfn[x] = ++ti] = x;
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (y != pre) {
      dep[y] = dep[x] + 1;
      s[y] = s[x] + G.edge[j].k;
      dfs(y, x);
      st[++ti] = x;
    }
  }
}
void init(int n) {
  dep[1] = s[1] = 0;
  dfs(1, 0);
  st.build(n + n + 1);
}
inline int lca(int x, int y) {
  if (dfn[x] > dfn[y]) swap(x, y);
  return st.query(dfn[x], dfn[y]);
}
inline long long dis(int x, int y) { return s[x] + s[y] - (s[lca(x, y)] << 1); }
}  // namespace T
int sz[N], val[N];
void get_sz(int x, int pre) {
  sz[x] = 1;
  val[x] = 0;
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (y != pre && !G.edge[j].mark) {
      get_sz(y, x);
      sz[x] += sz[y];
      chmax(val[x], sz[y]);
    }
  }
}
int get_rt(int x, int pre, int size) {
  int rt = x;
  chmax(val[x], size - sz[x]);
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (y != pre && !G.edge[j].mark) {
      int k = get_rt(y, x, size);
      if (val[k] < val[rt]) rt = k;
    }
  }
  return rt;
}
int revp[N], p[N], dc_fa[N], dc_id[N];
S f[N];
vector<S> f2[N];
void dfs(int x, int pre, long long dis, vector<pair<int, long long> >& g) {
  g.push_back(make_pair(revp[x], dis));
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (y != pre && !G.edge[j].mark) dfs(y, x, dis + G.edge[j].k, g);
  }
}
void dc(int x, int pre, int id) {
  get_sz(x, 0);
  x = get_rt(x, 0, sz[x]);
  get_sz(x, 0);
  dc_fa[x] = pre;
  dc_id[x] = id;
  vector<pair<int, long long> > g;
  g.reserve(sz[x]);
  dfs(x, 0, 0, g);
  f[x].init(g);
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (!G.edge[j].mark) {
      vector<pair<int, long long> > g;
      g.reserve(sz[y]);
      dfs(y, x, G.edge[j].k, g);
      S s2;
      s2.init(g);
      f2[x].push_back(s2);
      G.edge[j].mark = G.edge[j ^ 1].mark = 1;
      dc(y, x, (int)f2[x].size() - 1);
    }
  }
}
long long query(int l, int r, int x) {
  long long ret = f[x].query(l, r).first;
  int sx = x;
  for (int y = dc_fa[x]; y != 0; x = y, y = dc_fa[y]) {
    long long d = T::dis(sx, y);
    pair<long long, int> k = f[y].query(l, r), k2 = f2[y][dc_id[x]].query(l, r);
    ret += k.first - k2.first + (k.second - k2.second) * d;
  }
  return ret;
}
vector<int> tim[N];
int ti;
void change1(int x, int t, int i) {
  if (tim[x][t + 1] != ti) {
    if (t == -1)
      f[x].change(i);
    else
      f2[x][t].change(i);
    tim[x][t + 1] = ti;
  }
}
void change(int i) {
  ++ti;
  change1(p[i], -1, i);
  for (int x = p[i], y = dc_fa[x]; y != 0; x = y, y = dc_fa[y]) {
    change1(y, dc_id[x], i);
    change1(y, -1, i);
  }
  change1(p[i + 1], -1, i);
  for (int x = p[i + 1], y = dc_fa[x]; y != 0; x = y, y = dc_fa[y]) {
    change1(y, dc_id[x], i);
    change1(y, -1, i);
  }
  swap(p[i], p[i + 1]);
  swap(revp[p[i]], revp[p[i + 1]]);
}
int main() {
  int n, q;
  gi(n);
  gi(q);
  for (int i = 1; i <= n; ++i) gi(p[i]), revp[p[i]] = i;
  for (int i = 1; i < n; ++i) {
    int x, y, w;
    gi(x);
    gi(y);
    gi(w);
    G.add2(x, y, w);
  }
  T::init(n);
  dc(1, 0, 0);
  for (int i = 1; i <= n; ++i) tim[i].resize(f2[i].size() + 1);
  long long ans = 0;
  int G = (1 << 30) - 1;
  while (q--) {
    int op;
    gi(op);
    if (op == 1) {
      int l, r, v;
      gi(l);
      gi(r);
      gi(v);
      l = (ans & G) ^ l;
      r = (ans & G) ^ r;
      v = (ans & G) ^ v;
      pi(ans = query(l, r, v));
    } else {
      int x;
      gi(x);
      x ^= (ans & G);
      change(x);
    }
  }
  return 0;
}

### Prompt

Please formulate a cpp solution 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>
using namespace std;
const int N = 5 + 2e5;
template <class T>
void chmax(T& x, T y) {
  y > x ? x = y : T();
}
namespace IO {
const int sz = 1 << 20;
char a[sz + 5], b[sz + 5], *p1 = a, *p2 = a, *t = b, p[105];
inline char gc() {
  return getchar();
  return p1 == p2
             ? (p2 = (p1 = a) + fread(a, 1, sz, stdin), p1 == p2 ? EOF : *p1++)
             : *p1++;
}
template <class T>
void gi(T& x) {
  x = 0;
  char c = gc();
  for (; c < '0' || c > '9'; c = gc())
    ;
  for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
}
inline void flush() { fwrite(b, 1, t - b, stdout), t = b; }
inline void pc(char x) {
  *t++ = x;
  if (t - b == sz) flush();
}
template <class T>
void pi(T x, char c = '\n') {
  if (x < 0) pc('-'), x = -x;
  if (x == 0) pc('0');
  int t = 0;
  for (; x; x /= 10) p[++t] = x % 10 + '0';
  for (; t; --t) pc(p[t]);
  pc(c);
}
struct F {
  ~F() { flush(); }
} f;
}  // namespace IO
using IO::gi;
using IO::pi;
struct S {
  vector<pair<int, long long> > a;
  vector<long long> s;
  void init(vector<pair<int, long long> > _a) {
    a = _a;
    sort(a.begin(), a.end());
    s.resize(a.size());
    s[0] = a[0].second;
    for (int i = 1; i < a.size(); ++i) s[i] = s[i - 1] + a[i].second;
  }
  inline int search(int x) {
    int p = upper_bound(a.begin(), a.end(), make_pair(x, (long long)1e18)) -
            a.begin();
    return p - 1;
  }
  inline pair<long long, int> query(int x) {
    int p = search(x);
    if (p == -1)
      return make_pair(0ll, 0);
    else
      return make_pair(s[p], p + 1);
  }
  inline pair<long long, int> query(int l, int r) {
    pair<long long, int> a = query(r), b = query(l - 1);
    return make_pair(a.first - b.first, a.second - b.second);
  }
  inline void change(int x) {
    int p = search(x), p1;
    p1 = min(p + 1, (int)a.size() - 1);
    if (p == -1 || a[p].first != x) p = -1;
    if (p1 == -1 || a[p1].first != x + 1) p1 = -1;
    if (p != -1) a[p].first++;
    if (p1 != -1) a[p1].first--;
    if (p != -1 && p1 != -1) {
      s[p] += a[p1].second - a[p].second;
      swap(a[p], a[p1]);
    }
  }
};
struct Graph {
  struct Edge {
    int to, nxt, k;
    bool mark;
  } edge[N * 2];
  int head[N], top;
  Graph() { memset(head, -1, sizeof(head)), top = -1; }
  inline void add(int x, int y, int k) {
    edge[++top] = (Edge){y, head[x], k, false};
    head[x] = top;
  }
  inline void add2(int x, int y, int k) { add(x, y, k), add(y, x, k); }
} G;
namespace T {
int dfn[N], dep[N], ti = 0;
long long s[N];
inline int merge(int x, int y) { return dep[x] < dep[y] ? x : y; }
struct ST {
  int st[23][N + N], p[N + N];
  int& operator[](int x) { return st[0][x]; }
  void build(int n) {
    for (int l = 1; 1 << l <= n; ++l)
      for (int i = 1; i + (1 << l) - 1 <= n; ++i)
        st[l][i] = T::merge(st[l - 1][i], st[l - 1][i + (1 << l - 1)]);
    p[1] = 0;
    for (int i = 2; i <= n; ++i) p[i] = p[i >> 1] + 1;
  }
  int query(int x, int y) {
    int l = p[y - x + 1];
    return T::merge(st[l][x], st[l][y - (1 << l) + 1]);
  }
} st;
void dfs(int x, int pre) {
  st[dfn[x] = ++ti] = x;
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (y != pre) {
      dep[y] = dep[x] + 1;
      s[y] = s[x] + G.edge[j].k;
      dfs(y, x);
      st[++ti] = x;
    }
  }
}
void init(int n) {
  dep[1] = s[1] = 0;
  dfs(1, 0);
  st.build(n + n + 1);
}
inline int lca(int x, int y) {
  if (dfn[x] > dfn[y]) swap(x, y);
  return st.query(dfn[x], dfn[y]);
}
inline long long dis(int x, int y) { return s[x] + s[y] - (s[lca(x, y)] << 1); }
}  // namespace T
int sz[N], val[N];
void get_sz(int x, int pre) {
  sz[x] = 1;
  val[x] = 0;
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (y != pre && !G.edge[j].mark) {
      get_sz(y, x);
      sz[x] += sz[y];
      chmax(val[x], sz[y]);
    }
  }
}
int get_rt(int x, int pre, int size) {
  int rt = x;
  chmax(val[x], size - sz[x]);
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (y != pre && !G.edge[j].mark) {
      int k = get_rt(y, x, size);
      if (val[k] < val[rt]) rt = k;
    }
  }
  return rt;
}
int revp[N], p[N], dc_fa[N], dc_id[N];
S f[N];
vector<S> f2[N];
void dfs(int x, int pre, long long dis, vector<pair<int, long long> >& g) {
  g.push_back(make_pair(revp[x], dis));
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (y != pre && !G.edge[j].mark) dfs(y, x, dis + G.edge[j].k, g);
  }
}
void dc(int x, int pre, int id) {
  get_sz(x, 0);
  x = get_rt(x, 0, sz[x]);
  get_sz(x, 0);
  dc_fa[x] = pre;
  dc_id[x] = id;
  vector<pair<int, long long> > g;
  g.reserve(sz[x]);
  dfs(x, 0, 0, g);
  f[x].init(g);
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (!G.edge[j].mark) {
      vector<pair<int, long long> > g;
      g.reserve(sz[y]);
      dfs(y, x, G.edge[j].k, g);
      S s2;
      s2.init(g);
      f2[x].push_back(s2);
      G.edge[j].mark = G.edge[j ^ 1].mark = 1;
      dc(y, x, (int)f2[x].size() - 1);
    }
  }
}
long long query(int l, int r, int x) {
  long long ret = f[x].query(l, r).first;
  int sx = x;
  for (int y = dc_fa[x]; y != 0; x = y, y = dc_fa[y]) {
    long long d = T::dis(sx, y);
    pair<long long, int> k = f[y].query(l, r), k2 = f2[y][dc_id[x]].query(l, r);
    ret += k.first - k2.first + (k.second - k2.second) * d;
  }
  return ret;
}
vector<int> tim[N];
int ti;
void change1(int x, int t, int i) {
  if (tim[x][t + 1] != ti) {
    if (t == -1)
      f[x].change(i);
    else
      f2[x][t].change(i);
    tim[x][t + 1] = ti;
  }
}
void change(int i) {
  ++ti;
  change1(p[i], -1, i);
  for (int x = p[i], y = dc_fa[x]; y != 0; x = y, y = dc_fa[y]) {
    change1(y, dc_id[x], i);
    change1(y, -1, i);
  }
  change1(p[i + 1], -1, i);
  for (int x = p[i + 1], y = dc_fa[x]; y != 0; x = y, y = dc_fa[y]) {
    change1(y, dc_id[x], i);
    change1(y, -1, i);
  }
  swap(p[i], p[i + 1]);
  swap(revp[p[i]], revp[p[i + 1]]);
}
int main() {
  int n, q;
  gi(n);
  gi(q);
  for (int i = 1; i <= n; ++i) gi(p[i]), revp[p[i]] = i;
  for (int i = 1; i < n; ++i) {
    int x, y, w;
    gi(x);
    gi(y);
    gi(w);
    G.add2(x, y, w);
  }
  T::init(n);
  dc(1, 0, 0);
  for (int i = 1; i <= n; ++i) tim[i].resize(f2[i].size() + 1);
  long long ans = 0;
  int G = (1 << 30) - 1;
  while (q--) {
    int op;
    gi(op);
    if (op == 1) {
      int l, r, v;
      gi(l);
      gi(r);
      gi(v);
      l = (ans & G) ^ l;
      r = (ans & G) ^ r;
      v = (ans & G) ^ v;
      pi(ans = query(l, r, v));
    } else {
      int x;
      gi(x);
      x ^= (ans & G);
      change(x);
    }
  }
  return 0;
}

```