A rooted tree is being built. Initially, there is only one node in the tree, having number 1 and value 0. You are to perform Q (Q<=200000) queries, each of them is one of the following two types:

• 1 X Y - Add a new vertex to the tree with parent X (It's guaranteed that node X is already in the tree) and value Y (1<=Y<=10^9). Its number will be the smallest positive integer that is not a number of a node yet. For example, the first query of this type will add a vertex with number 2, then 3, then 4 and so on.
• 2 X - Consider the children of node X. For each of them, let's sum up the values of all nodes in their subtrees. You are asked to print the maximum of those sums.

Input

The first line contains an integer Q - the number of queries. Each of the next Q lines contains one of the queries.

Output

Print the answers for all queries of the second type, one answer per line.

Example

Input:
7
1 1 3
2 1
2 2
1 2 5
2 1
1 1 4
2 1

Output:
3
0
8
8