Idols and Fans

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Mike is a cool kid, so he's the most popular person in his school. All the girls want to be with him while all the boys want to be like him.
There are N persons in Mike's school. No person in the school has a name(except Mike), but all of them have a unique ID integer number for the range[1..N]. Mike's ID equals to 1. Also, each person(except Mike) has his/her personal idol, who is another person from the school. Finally, each person X has an integer number A_{X}.
Let's define functions F and G for a person with ID equals to X:
 If X = 1(which means that person X is Mike), then F_{X} = A_{X} and G_{X} = 1;
 Otherwise, let Y be the personal idol for X.
 If F_{Y} + 1 < A_{X}, then F_{X} = A_{X} and G_{X} = 1;
 If F_{Y} + 1 > A_{X}, then F_{X} = F_{Y} + 1 and G_{X} = G_{Y};
 If F_{Y} + 1 = A_{X}, then F_{X} = F_{Y} + 1 and G_{X} = G_{Y} + 1.
It's guaranteed, that it's possible to calculate functions F and G for every person in the school.
You are to write a program, that can efficiently process queries of the following types:
 0 X NEW_VALUE  change the value of A_{X} to NEW_VALUE;
 1 X  calculate F_{X} and G_{X}.
Input
The first line of the input contains two integers N and Q, denoting the number of the persons in Mike's school and the number of queries to process.
The second line contains N integers A_{i}, denoting A_{1}, A_{2}, ..., A_{N}.
The third line contains N  1 integers P_{i}, denoting the personal idols of persons with IDs equal to 2, 3, ..., N. 1 ≤ P_{i} < i.
The next Q lines contain information about the queries. The format of the queries is the same with the one described in the statement.
Output
For each query of the second type, output a single line containing two integers, F_{X} and G_{X}.
Constraints
1 ≤ N ≤ 100000;
1 ≤ Q ≤ 300000;
1 ≤ A_{i} ≤ 10^{9}, for each person;
1 ≤ X ≤ N, 1 ≤ NEW_VALUE ≤ 10^{9}, for each query of the first type.
Example
Input: 5 2 1 2 3 4 5 1 2 3 4 1 5 0 1 100 Output: 5 5
Explanations
In the input, before the second query, F's and G's equals to the following:
ID  F  G 
1  1  1 
2  2  2 
3  3  3 
4  4  4 
5  5  5 
After the second query, F's and G's equals to the following:
ID  F  G 
1  100  1 
2  101  1 
3  102  1 
4  103  1 
5  104  1 
Author:  kostya_by 
Tester:  rustinpiece 
Editorial  http://discuss.codechef.com/problems/IDOLS 
Tags  cook47, hard, heavylight, kostya_by, segmenttree 
Date Added:  31052014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 