SAMBOX - Samvel and Boxes


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 a1 ... an-1. ai-1 is the index of the box that contains box i. (1 ≤ ai ≤ 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

hide comments
nivedit_jain: 2019-10-05 07:08:14

very weak test cases.

mananshah2709: 2019-09-27 23:55:46

This question is good but test cases are very weak as brute force works for it

Last edit: 2019-10-03 23:21:10
kumar0916: 2019-09-24 23:09:09

Nice Problem

Last edit: 2019-09-24 23:10:19
khachdallak: 2018-05-07 13:51:56

Very good problem!!!

samand: 2018-04-30 15:21:43

Thank you for this beautiful and educational problem.

alexandro5432: 2018-04-26 15:38:33

I am very sorry for 1 wrong test case. Please resubmit your solutions.
P.S.I have removed from status all solutions that were made before fixing the test cases.

Last edit: 2018-04-26 15:43:41
[Rampage] Blue.Mary: 2018-04-24 10:46:34

I've made the following assumption:
(1)For all type of queries, "x-th box" in problem statement means "the box with index x", since the index of the box may change according to query type 2.
(2)In query type 3, it requires the number of all apples in "x-th box", directly or indirectly.
(3)In query type 4, it requires "query type 3" to the box with minimum index directly inside "x-th box".

Are these assumptions right?

Last edit: 2019-04-13 15:34:58

Added by:AlAbelyan
Date:2018-04-18
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:my own