Problem Description

Joisino noticed that she was sitting in front of her TV at home.
Was she dreaming before?
It seemed like she had been watching TV for quite some time, and the clock on the wall indicated that it was an hour before her work was supposed to start.

Fortunately, the city office where Joisino works is very close to her home.
So, Joisino arrived at her workplace leisurely, only to be informed that she had been assigned to the road maintenance department.

The city is currently undergoing very active urban development, which has led to concerns about worsening traffic conditions.
Therefore, the city decided to entrust Joisino with understanding the traffic situation.

At the moment, there is only one city in the municipality.
However, it is expected that the number of cities will increase due to urban development.
When a new city is created, an existing city is chosen, and a road is built between the new and the existing city.
Thus, at all times, if the number of cities is $ n $, there are $ n-1 $ roads.
Additionally, the initial city is called City $ 0 $, the $ i(1 ≦ i) $th city created is called City $ i $, and the $ i(1 ≦ i) $th road created is called Road $ i $.

Furthermore, since the population of each city is also changing, the required time for each road is also changing.
In addition, it is necessary to know the required time to the city that takes the longest to reach from a certain city for the improvement of residents' convenience.

Under such circumstances, Joisino is given $ Q $ queries about the cities.
The $ i(1 ≦ i ≦ Q) $th information is one of the following three types:

• Query 1: A new city is created, and it is connected to City $ A_i $ with a road of required time $ C_i $.
• Query 2: The required time of Road $ A_i $ has changed to $ C_i $.
• Query 3: It is necessary to know the required time to the city that takes the longest to reach from City $ A_i $.

Among these, when Query 3 comes, you must answer it.

However, this task is very troublesome, and if done manually, it would mean living at the workplace.
Therefore, Joisino decided to write a program to have this work done on her behalf.

Input Format

The input is given from the standard input in the following format:

$ Q $ $ T_1 $ $ A_1 $ $ C_1 $ $ T_2 $ $ A_2 $ $ C_2 $ : $ T_Q $ $ A_Q $ $ C_Q $

• The first line contains the number of queries $ Q(1 ≦ Q ≦ 5*10^5) $.
• The next $ Q $ lines contain the $ i $th query, where the $ i $th line contains $ T_i(1 ≦ T_i ≦ 3), A_i(0 ≦ A_i ≦ number of existing cities - 1), C_i $ separated by spaces.
• $ T_i $ represents the type of query.
• When $ T_i = 1 $, a new city is created, and it is connected to City $ A_i $ with a road of required time $ C_i(1 ≦ C_i ≦ 10^9) $.
• When $ T_i = 2 $, the required time of Road $ A_i $ has changed to $ C_i(1 ≦ C_i ≦ 10^9) $.
• When $ T_i = 3 $, it is necessary to know the required time to the city that takes the longest to reach from City $ A_i $. $ C_i $ can be ignored. Also, if there is only one city, the answer is 0.

Output Format

The output has as many lines as there are Query 3s.
The $ i $th line should contain the answer to the $ i $th Query 3.
Ensure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

6
1 0 10
1 1 7
3 1 0
2 2 5
1 0 17
3 0 0

Sample Output #1

10
17

Sample Input #2

7
3 0 0
1 0 10
2 1 15
1 0 7
1 2 5
1 2 8
3 0 0

Sample Output #2

0
15

Sample Input #3

10
1 0 234
1 1 354
2 1 145
2 1 456
2 1 51
3 0 0
1 0 352
3 0 0
2 1 234
3 3 0

Sample Output #3

None

Notes/Hints

Scoring

This problem has partial points.

• Dataset 1 satisfies $ Q ≦ 10^4 $, and correct answers to this will earn 5 points.
• Dataset 2 has no additional constraints, and correct answers to this will earn 155 points.

见题面 Input 部分

见题面 Output 部分