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 $*a*_{1}, *a*_{2}..., *a*_{*n*}$ 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 , 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 $*a*_{*x*}$ and $*a*_{*x* + 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·10^{5}$, $1 ≤ *q* ≤ 2·10^{5}$) — the number of nodes in the tree and the number of queries, respectively.

The next line contains $*n*$ space-separated integers — the sequence $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ 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* ≤ 10^{6}$). 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* < 2^{30}$) using which $*l*$, $*r*$ and $*v*$ can be generated using the formula given below:
• ,
  • ,
  • .
• t = 2: Second line contains single integer $*a*$ ($1 ≤ *a* < 2^{30}$) using which $*x*$ can be generated using the formula given below:
• .

The $*ans*_{*i*}$ is the answer for the $*i*$-th query, assume that $*ans*_{0} = 0$. If the $*i*$-th query is of type 2 then $*ans*_{*i*}$ = $*ans*_{*i* - 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 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.

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