Given a tree of size $n$ rooted at $1$, the tree is provided as follows: input $a_2, a_3, \dots, a_n$, where it is guaranteed that $1 \leq a_i < i$. An edge is formed between $a_i$ and $i$ to construct the tree.

There are $m$ operations of two types:

• 1 l r x: Set $a_i = \max(a_i - x, 1)$ for $l \leq i \leq r$.
• 2 u v: Query the LCA of $u$ and $v$ in the tree formed by the current array $a$.

Input

The first line contains two integers $n$ and $m$.

The next line contains $n-1$ integers, representing $a_2, \dots, a_n$.

The following $m$ lines each contain three or four integers, representing an operation.

This problem is strictly online. All input values $l, r, x, u, v$ must be XORed with $lastans$, which is defined as the answer to the previous query operation. If there has been no query operation yet, $lastans$ is $0$.

Output

For each type $2$ operation, output one integer per line representing the answer.

Examples

Input 1

6 4
1 2 3 3 4
2 3 4
1 1 0 2
2 6 5
2 1 0

Output 1

3
3
1

Subtasks

Idea: Ynoi, Solution: Ynoi, Code: Ynoi, Data: Ynoi & nzhtl1477

For $100\%$ of the data, $2 \leq n, q \leq 4 \times 10^5$, $2 \leq l \leq r \leq n$, $1 \leq x \leq 4 \times 10^5$, and $1 \leq u, v \leq n$.