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 ai(1≤ai<i) for (2≤i≤n).
There are two types of q queries to be executed:
You are given three integers l,r and x(2≤l≤r≤n,1≤x≤105). You should replace ai with max(ai−x,1) for all i with l≤i≤r.
You are given two integers u,v(1≤u,v≤n). You must find the LCA of the vertices u and v (their lowest common ancestor).
The first line contains two integers n and q(2≤n,q≤105) — the number of vertices and the number of queries, respectively.
The second line contains n−1 integers a2,a3,...,an(1≤ai<i), where ai 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≤l≤r≤n,1≤x≤105), which means that you need to replace ai with max(ai−x,1) for all i with l≤i≤r.
If t=2, then this is a request of the second type. Then two integers will follow: u and v(1≤u,v≤n), and you should find LCA u and v.
It is guaranteed that there is at least one request of the second type.
For each request of the second type, print the answer in a new line.