No legend

You are given a tree that has $n$ vertices, with a root of $1$.

We assume that the immediate parent of the vertex $i$ is $a_i(1\le a_i<i)$ for $(2\le i\le n)$.

There are two types of $q$ queries to be executed:

• You are given three integers $l,r$ and $x(2\le l\le r\le n,1\le x\le 10^5)$. You should replace $a_i$ with $max(a_i-x,1)$ for all $i$ with $l\le i\le r$.

• You are given two integers $u,v(1\le u,v\le n)$. You must find the LCA of the vertices $u$ and $v$ (their lowest common ancestor).

Input

The first line contains two integers $n$ and $q(2\le n,q\le 10^5)$ — the number of vertices and the number of queries, respectively.

The second line contains $n-1$ integers $a_2,a_3,...,a_n(1\le a_i<i)$, where $a_i$ is the parent of the node $i$.

The following $q$ rows contain queries. For each query, the first integer of the string is $t(t=1$ or $2)$ query type.

If $t=1$, then this is a request of the first type. Then three integers will follow: $l,r,x(2\le l\le r\le n,1\le x\le 10^5)$, which means that you need to replace $a_i$ with $max(a_i-x,1)$ for all $i$ with $l\le i\le r$.

If $t=2$, then this is a request of the second type. Then two integers will follow: $u$ and $v(1\le u,v\le n)$, and you should find LCA $u$ and $v$.

It is guaranteed that there is at least one request of the second type.

Output

For each request of the second type, print the answer in a new line.

Examples