#include <bits/stdc++.h>
struct InputOutputStream {
  enum { SIZE = 1 << 18 | 1 };
  char ibuf[SIZE], *s, *t, obuf[SIZE], *oh;
  InputOutputStream() : s(), t(), oh(obuf) {}
  ~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
  inline char read() {
    return (s == t) && (t = (s = ibuf) + fread(ibuf, 1, SIZE, stdin)),
           s == t ? -1 : *s++;
  }
  template <typename T>
  inline InputOutputStream &operator>>(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
      if (c == -1) return *this;
      iosig |= c == '-';
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig && (x = -x);
    return *this;
  }
  inline void print(char c) {
    (oh == obuf + SIZE) && (fwrite(obuf, 1, SIZE, stdout), oh = obuf);
    *oh++ = c;
  }
  template <typename T>
  inline void print(T x) {
    static int buf[21], cnt;
    if (x != 0) {
      (x < 0) && (print('-'), x = -x);
      for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
      while (cnt) print((char)buf[cnt--]);
    } else {
      print('0');
    }
  }
  template <typename T>
  inline InputOutputStream &operator<<(const T &x) {
    print(x);
    return *this;
  }
} io;
const int MAXN = 200000 + 1;
const int MAXG = MAXN * 2 + 1;
const int MAX_LOG = 19;
int n, q;
struct Edge {
  int v, w;
  Edge(int v, int w) : v(v), w(w) {}
};
std::vector<Edge> edge[MAXN], g[MAXG];
int a[MAXN];
int tot;
inline void addEdge(int u, int v, int w) {
  g[u].emplace_back(v, w);
  g[v].emplace_back(u, w);
}
inline void binarize(int u, int pre) {
  static std::vector<Edge *> now;
  now.clear();
  for (auto &p : edge[u])
    if (p.v != pre) now.push_back(&p);
  int o = u;
  for (int i = 0; i < (int)now.size(); i++) {
    addEdge(o, now[i]->v, now[i]->w);
    if (now.size() - i > 2) {
      addEdge(o, ++tot, 0);
      o = tot;
    }
  }
  for (auto &p : edge[u])
    if (p.v != pre) binarize(p.v, u);
}
bool vis[MAXG];
int sz[MAXG], idx[MAXG][MAX_LOG], dep[MAXG];
long long dis[MAXG][MAX_LOG];
void dfsSize(int u, int pre) {
  sz[u] = 1;
  for (auto &p : g[u]) {
    if (!vis[p.v] && p.v != pre) {
      dfsSize(p.v, u);
      sz[u] += sz[p.v];
    }
  }
}
int get(int u, int pre, int n) {
  for (auto &p : g[u])
    if (!vis[p.v] && p.v != pre && sz[p.v] > n) return get(p.v, u, n);
  return u;
}
void dfs(int u, int pre, int d) {
  for (auto &p : g[u]) {
    if (!vis[p.v] && p.v != pre) {
      idx[p.v][d] = idx[u][d];
      dis[p.v][d] = dis[u][d] + p.w;
      dfs(p.v, u, d);
    }
  }
}
void build(int u, int d) {
  dfsSize(u, 0);
  vis[u = get(u, 0, sz[u] / 2)] = true;
  dep[u] = d;
  int c = 0;
  for (auto &p : g[u]) {
    if (!vis[p.v]) {
      dis[p.v][d] = p.w;
      idx[p.v][d] = c++;
      dfs(p.v, u, d);
      build(p.v, d + 1);
    }
  }
}
char *cur;
struct Node *null;
struct Node {
  static const int NODE_SIZE;
  Node *c[3];
  int sz;
  long long sum;
};
const int Node::NODE_SIZE = sizeof(Node);
const int MAXM = MAXG * MAX_LOG * 2;
char pool[Node::NODE_SIZE];
void insert(Node *&p, Node *pre, int u, int d) {
  p = new Node(*pre);
  p->sz++;
  p->sum += dis[u][d] - dis[u][d - 1];
  if (d != dep[u]) insert(p->c[idx[u][d]], pre->c[idx[u][d]], u, d + 1);
}
void erase(Node *&p, Node *pre, int u, int d) {
  p = new Node(*pre);
  p->sz--;
  p->sum -= dis[u][d] - dis[u][d - 1];
  if (d != dep[u]) erase(p->c[idx[u][d]], pre->c[idx[u][d]], u, d + 1);
}
long long query(Node *p, int u, int d) {
  return ((d == dep[u] || p == null) ? 0 : query(p->c[idx[u][d]], u, d + 1)) +
         p->sum + p->sz * (dis[u][d] - dis[u][d - 1]);
}
Node *root[MAXG];
int main() {
  cur = pool;
  null = (Node *)pool;
  null->c[0] = null->c[1] = null->c[2] = null;
  io >> n >> q;
  for (int i = 1; i <= n; i++) io >> a[i];
  for (int i = 1, u, v, w; i < n; i++) {
    io >> u >> v >> w;
    edge[u].emplace_back(v, w);
    edge[v].emplace_back(u, w);
  }
  tot = n;
  binarize(1, 0);
  build(1, 1);
  for (int i = 0; i <= n; i++) root[i] = null;
  for (int i = 1; i <= n; i++) insert(root[i], root[i - 1], a[i], 1);
  long long lastans = 0;
  for (int cmd, l, r, u; q--;) {
    io >> cmd;
    switch (cmd) {
      case 1: {
        io >> l >> r >> u;
        l ^= lastans;
        r ^= lastans;
        u ^= lastans;
        lastans = query(root[r], u, 1) - query(root[l - 1], u, 1);
        io << lastans << '\n';
        lastans &= ((1 << 30) - 1);
        break;
      }
      case 2: {
        io >> u;
        u ^= lastans;
        erase(root[u], root[u], a[u], 1);
        std::swap(a[u], a[u + 1]);
        insert(root[u], root[u], a[u], 1);
        break;
      }
    }
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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>
struct InputOutputStream {
  enum { SIZE = 1 << 18 | 1 };
  char ibuf[SIZE], *s, *t, obuf[SIZE], *oh;
  InputOutputStream() : s(), t(), oh(obuf) {}
  ~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
  inline char read() {
    return (s == t) && (t = (s = ibuf) + fread(ibuf, 1, SIZE, stdin)),
           s == t ? -1 : *s++;
  }
  template <typename T>
  inline InputOutputStream &operator>>(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
      if (c == -1) return *this;
      iosig |= c == '-';
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig && (x = -x);
    return *this;
  }
  inline void print(char c) {
    (oh == obuf + SIZE) && (fwrite(obuf, 1, SIZE, stdout), oh = obuf);
    *oh++ = c;
  }
  template <typename T>
  inline void print(T x) {
    static int buf[21], cnt;
    if (x != 0) {
      (x < 0) && (print('-'), x = -x);
      for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
      while (cnt) print((char)buf[cnt--]);
    } else {
      print('0');
    }
  }
  template <typename T>
  inline InputOutputStream &operator<<(const T &x) {
    print(x);
    return *this;
  }
} io;
const int MAXN = 200000 + 1;
const int MAXG = MAXN * 2 + 1;
const int MAX_LOG = 19;
int n, q;
struct Edge {
  int v, w;
  Edge(int v, int w) : v(v), w(w) {}
};
std::vector<Edge> edge[MAXN], g[MAXG];
int a[MAXN];
int tot;
inline void addEdge(int u, int v, int w) {
  g[u].emplace_back(v, w);
  g[v].emplace_back(u, w);
}
inline void binarize(int u, int pre) {
  static std::vector<Edge *> now;
  now.clear();
  for (auto &p : edge[u])
    if (p.v != pre) now.push_back(&p);
  int o = u;
  for (int i = 0; i < (int)now.size(); i++) {
    addEdge(o, now[i]->v, now[i]->w);
    if (now.size() - i > 2) {
      addEdge(o, ++tot, 0);
      o = tot;
    }
  }
  for (auto &p : edge[u])
    if (p.v != pre) binarize(p.v, u);
}
bool vis[MAXG];
int sz[MAXG], idx[MAXG][MAX_LOG], dep[MAXG];
long long dis[MAXG][MAX_LOG];
void dfsSize(int u, int pre) {
  sz[u] = 1;
  for (auto &p : g[u]) {
    if (!vis[p.v] && p.v != pre) {
      dfsSize(p.v, u);
      sz[u] += sz[p.v];
    }
  }
}
int get(int u, int pre, int n) {
  for (auto &p : g[u])
    if (!vis[p.v] && p.v != pre && sz[p.v] > n) return get(p.v, u, n);
  return u;
}
void dfs(int u, int pre, int d) {
  for (auto &p : g[u]) {
    if (!vis[p.v] && p.v != pre) {
      idx[p.v][d] = idx[u][d];
      dis[p.v][d] = dis[u][d] + p.w;
      dfs(p.v, u, d);
    }
  }
}
void build(int u, int d) {
  dfsSize(u, 0);
  vis[u = get(u, 0, sz[u] / 2)] = true;
  dep[u] = d;
  int c = 0;
  for (auto &p : g[u]) {
    if (!vis[p.v]) {
      dis[p.v][d] = p.w;
      idx[p.v][d] = c++;
      dfs(p.v, u, d);
      build(p.v, d + 1);
    }
  }
}
char *cur;
struct Node *null;
struct Node {
  static const int NODE_SIZE;
  Node *c[3];
  int sz;
  long long sum;
};
const int Node::NODE_SIZE = sizeof(Node);
const int MAXM = MAXG * MAX_LOG * 2;
char pool[Node::NODE_SIZE];
void insert(Node *&p, Node *pre, int u, int d) {
  p = new Node(*pre);
  p->sz++;
  p->sum += dis[u][d] - dis[u][d - 1];
  if (d != dep[u]) insert(p->c[idx[u][d]], pre->c[idx[u][d]], u, d + 1);
}
void erase(Node *&p, Node *pre, int u, int d) {
  p = new Node(*pre);
  p->sz--;
  p->sum -= dis[u][d] - dis[u][d - 1];
  if (d != dep[u]) erase(p->c[idx[u][d]], pre->c[idx[u][d]], u, d + 1);
}
long long query(Node *p, int u, int d) {
  return ((d == dep[u] || p == null) ? 0 : query(p->c[idx[u][d]], u, d + 1)) +
         p->sum + p->sz * (dis[u][d] - dis[u][d - 1]);
}
Node *root[MAXG];
int main() {
  cur = pool;
  null = (Node *)pool;
  null->c[0] = null->c[1] = null->c[2] = null;
  io >> n >> q;
  for (int i = 1; i <= n; i++) io >> a[i];
  for (int i = 1, u, v, w; i < n; i++) {
    io >> u >> v >> w;
    edge[u].emplace_back(v, w);
    edge[v].emplace_back(u, w);
  }
  tot = n;
  binarize(1, 0);
  build(1, 1);
  for (int i = 0; i <= n; i++) root[i] = null;
  for (int i = 1; i <= n; i++) insert(root[i], root[i - 1], a[i], 1);
  long long lastans = 0;
  for (int cmd, l, r, u; q--;) {
    io >> cmd;
    switch (cmd) {
      case 1: {
        io >> l >> r >> u;
        l ^= lastans;
        r ^= lastans;
        u ^= lastans;
        lastans = query(root[r], u, 1) - query(root[l - 1], u, 1);
        io << lastans << '\n';
        lastans &= ((1 << 30) - 1);
        break;
      }
      case 2: {
        io >> u;
        u ^= lastans;
        erase(root[u], root[u], a[u], 1);
        std::swap(a[u], a[u + 1]);
        insert(root[u], root[u], a[u], 1);
        break;
      }
    }
  }
  return 0;
}

```