Dynamic Tree LCA with Updates

Given a tree with n nodes (numbered 1 through n) where node 1 is the root, the tree is initially defined by an array of parent pointers a₂, a₃, …, a_n such that for each i (2 ≤ i ≤ n), 1 ≤ a_i < i. An edge is formed between a_i and i for 2 ≤ i ≤ n.

You will then be given m operations. Each operation is one of the following two types:

• 1 l r x: For every index i in the interval [l, r] (with the condition that the parent pointer is defined for node i when i ≥ 2), update the parent pointer as follows:
  \( a_i = \max(a_i - x, 1) \)
• 2 u v: Query the lowest common ancestor (LCA) of nodes u and v in the current tree defined by the updated parent array.

The LCA of two nodes in a rooted tree is defined as the deepest (i.e. farthest from the root) node that is an ancestor of both nodes. Note that update operations might change the tree structure.

inputFormat

The first line contains two integers n and m — the number of nodes and the number of operations respectively.

The second line contains n - 1 integers: a₂, a₃, …, a_n, where for each i (2 ≤ i ≤ n), 1 ≤ a_i < i.

The next m lines each describe an operation in one of the following formats:

• 1 l r x (1 ≤ l ≤ r ≤ n, x is a positive integer)
• 2 u v (1 ≤ u, v ≤ n)

outputFormat

For each operation of type 2, output the LCA of nodes u and v on a new line.

sample

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

1
1
1