King of Boxes Robert wants to test Samvel.  He has given Samvel n boxes indexed from 1 to n. All the boxes except the first one are located in another box. Robert wants to fill the boxes with apples (At beginning boxes contain no apples).  Robert can ask Samvel queries of 4 types.

The queries are

1) Robert says two integers x,y to Samvel. Samvel needs to add x (1≤x≤10^9) apples to the y-th box. (1≤y≤n)

2) Robert says two integers x,y to Samvel. Samvel needs to swap the indexes of the x-th and y-th boxes. (1≤x,y≤n)

3) Robert says an integer x to Samvel. Samvel needs to say the number of apples located in the box x (1≤x≤n) and in the boxes that are in the box x (directly or indirectly).

4) Robert says an integer x to Samvel. Samvel needs to answer the query of the third type for the box that has minimum index from the boxes that are located directly in the box x. (1≤x≤n)

Samvel needs your help. help him and write a program to answer this queries.

Input

The first line of input contains an integer n (2≤n≤10^5)  and q (1≤q≤10^5), number of boxes and number of queries.

Second line contains n-1 integers a₁...a_n-1. a_i-1 is the index of the box that contains box i. (1≤a_i≤n)

The lines from 3 to q+2 contain an integer k (type of the query). if k=1 or k=2 then goes the two integer x,y from the task, else there is only one integer x.

Output

For each query of type 3 or 4 you need to output one integer the answer of query in a seperate line. If query type is 4 and given box has no oher boxes in it print -1.

Example

Input:
4 6
1 1 2
1 5 1
3 1
2 1 3
3 3
1 60 1
4 3

Output:
5
5
60