Yuezheng Ling and Dynamic Tree

Yuezheng 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 ≤ a_i<i for 2 ≤ i ≤ n), and she will ask you to perform q queries of 2 types:

1. She'll give you three integers l, r and x (2 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5). You need to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.
2. She'll give you two integers u, v (1 ≤ u, v ≤ 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≤ n,q ≤ 10^5) — the number of nodes and the number of queries, respectively.

The second line contains n-1 integers a_2, a_3,..., a_n (1 ≤ 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 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5), meaning that you have to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.

If t = 2, this represents the query of the second type. Then, two integers will follow: u and v (1 ≤ u, v ≤ 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.

inputFormat

Input

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

The second line contains n-1 integers a_2, a_3,..., a_n (1 ≤ 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 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5), meaning that you have to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.

If t = 2, this represents the query of the second type. Then, two integers will follow: u and v (1 ≤ u, v ≤ 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.

outputFormat

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.

样例

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

3
3
1

</p>