Statement:

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

Example output:

3 0 8 8

Time and memory limit:

- 2s
- 128MB

**Problem source:** Sphere Online Judge