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 yth box. (1≤y≤n)
2) Robert says two integers x,y to Samvel. Samvel needs to swap the indexes of the xth and yth 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 querie 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 n1 integers a_{1}...a_{n1}. a_{i1} 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 querie). 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 querie of type 3 or 4 you need to output one integer the answer of querie 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
aditya12legend:
20180509 19:25:08
Can someone provide with Sample Test Cases ?? 

khachdallak:
20180507 13:51:56
Very good problem!!! 

samand:
20180430 15:21:43
Thank you for this beautiful and educational problem. 

alexandro5432:
20180426 15:38:33
I am very sorry for 1 wrong test case. Please resubmit your solutions.


[Rampage] Blue.Mary:
20180424 10:46:34
I've made the following assumption:


rkocharyan:
20180419 20:58:04
Nice problem! Last edit: 20180507 14:28:14 
Added by:  Abelyan 
Date:  20180418 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  my own 