Description

You are given a rooted tree with $n$ nodes, rooted at $1$, with edge weights, and there are $m$ operations.

1. Query the $k$-th smallest depth value among nodes in the subtree of $x$. If the subtree has fewer than $k$ nodes, output $-1$.
2. Add $k$ to the weight of the edge between $x$ and its parent.

It is guaranteed that in every operation 2, the value $k$ and all original edge weights in the tree are less than or equal to a number $len$.

If $x$ is $1$ in operation 2, then it is treated as adding $k$ to the base depth of $x$.

Input Format

The first line contains three integers $n$, $m$, and $len$.

The next $n - 1$ lines each contain two integers, describing for nodes $2$~$n$ the parent of each node and the weight of the edge to its parent.

The next $m$ lines each contain three integers $opt$, $x$, and $k$. Here $opt$ denotes the operation type, and $x$, $k$ have the meanings described above.

Output Format

For each operation of type 1, output a single integer representing the answer.

3 5 3
1 3
2 3
1 1 3
2 3 3
1 1 3
2 1 2
1 1 3

6
9
11

Hint

Constraints and Hints

For 10% of the testdata, $n, m \leq 1000$.

For 30% of the testdata, $n, m \leq 30000$.

For 100% of the testdata, $n, m \leq 100000, len \leq 10$.

This easy problem uses bundled testdata. You can only receive the points for a subtask if you pass all testdata in that subtask.

If you are not interested in Shankouding (pinyin) and G&P, you can ignore the ending.

If you solved this problem:

The girls read your STD and all got AC on this problem, then went to help the war goddess.

They found 30 “183”s and blasted the enemy in the face.

If you didn’t solve this problem:

Although the girls really wanted to help the war goddess, they couldn’t. After all, learning Sensha-dō doesn’t grant direct admissions.

There was no other way; they had to fight 8 versus 30.

The Rheinmetall camped in the bushes. No one on the University Team spotted it. After it destroyed five enemy tanks, its hull couldn’t withstand the gun’s recoil and it fell apart.

The StuG III also camped in the bushes. No one on the University Team spotted it, and it didn’t spot anyone either. In the end it couldn’t sit still, charged forward, destroyed a Pershing, and was then destroyed.

The Waffenträger reversed artistically. The University Team was dumbfounded when they saw it. After it destroyed eight enemy tanks, its hull couldn’t withstand the gun’s recoil and it fell apart.

The Tiger (P) took out the 95 with a single shot, then burned down due to an engine failure during repositioning.

Finally, the French B1 fixed bayonets and stabbed 15 of them, turning the game around.

Translated by ChatGPT 5