Problem Description

Given a rooted tree of size $n$ with node $1$ as the root. The tree is given in the following way: you are given $a_2,a_3,\dots,a_n$, and it is guaranteed that $1\leq a_i<i$. Add an edge between $a_i$ and $i$ to form a tree.

Then there are $m$ operations of two types:

• 1 l r x Set $a_i=\max(a_i-x,1)$ for all $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 Format

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

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

Then follow $m$ lines, each containing three or four integers, representing one operation.

This problem is forced online. All inputs $l,r,x,u,v$ must be XORed with $lastans$, where $lastans$ is defined as the answer of the previous query operation. If there has been no query operation before, then it is $0$.

Output Format

For each operation of type $2$, output one line with one integer as the answer.

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

3
3
1

Hint

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

For $100\%$ of the testdata, it holds that $2\leq n,m\leq 4\times 10^5$, $2\leq l\leq r\leq n$, $1\leq x\leq 4\times 10^5$, $1\leq u,v\leq n$.

Translated by ChatGPT 5