Codeforces Global Round 13 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

trees

*3400

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. Yuezheng Ling and Dynamic Tree

time limit per test

1.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYuezheng Ling gives Luo Tianyi a tree which has $$$n$$$ nodes, rooted at $$$1$$$.

Luo Tianyi will tell you that the parent of the $$$i$$$-th node is $$$a_i$$$ ($$$1 \leq a_i<i$$$ for $$$2 \le i \le n$$$), and she will ask you to perform $$$q$$$ queries of $$$2$$$ types:

- She'll give you three integers $$$l$$$, $$$r$$$ and $$$x$$$ ($$$2 \le l \le r \le n$$$, $$$1 \le x \le 10^5$$$). You need to replace $$$a_i$$$ with $$$\max(a_i-x,1)$$$ for all $$$i$$$ with $$$l \leq i \leq r$$$.
- She'll give you two integers $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$). You need to find the LCA of nodes $$$u$$$ and $$$v$$$ (their lowest common ancestor).

Input

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

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

Next $$$q$$$ lines contain queries. For each query, the first integer of each line is $$$t$$$ ($$$t = 1$$$ or $$$2$$$) — the type of the query.

If $$$t = 1$$$, this represents the query 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$$$), meaning that you have to replace $$$a_i$$$ with $$$\max(a_i-x,1)$$$ for all $$$i$$$ with $$$l \leq i \leq r$$$.

If $$$t = 2$$$, this represents the query of the second type. Then, two integers will follow: $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), and you have to find the LCA of $$$u$$$ and $$$v$$$.

It's guaranteed that there is at least one query of the second type.

Output

For each query of the second type output answer on a new line.

Example

Input

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

Output

3 3 1

Note

The tree in example is shown below.

After the query of the first type, the tree changes and is looking as shown below.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2023 14:43:06 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|