Tree Depth Queries and Updates

You are given a rooted tree with \(n\) nodes numbered from 1 to \(n\), where node 1 is the root. The tree is weighted: for every node \(i\) (\(i>1\)) there is an edge between \(i\) and its parent with an associated weight. Initially, the depth of node 1 is \(0\), and for any other node \(i\) its depth is defined recursively as

[ depth(i)=depth(parent(i))+w(parent(i),i), ]

You are also given an integer \(len\) such that each update value and the original edge weights are not greater than \(len\). There are \(m\) operations, each of which is one of the following types:

1. Query: Given two integers \(x\) and \(k\), find the \(k\)-th smallest depth value among all nodes in the subtree of node \(x\) (including \(x\) itself). If the subtree contains fewer than \(k\) nodes, output \(-1\).
2. Update: Given two integers \(x\) and \(k\), add \(k\) to the weight of the edge connecting node \(x\) and its parent. If \(x=1\), then this operation is interpreted as adding \(k\) to the baseline depth of node 1 (affecting the depth of every node in the tree accordingly).

Note: The depth of each node is updated dynamically after each update operation.

inputFormat

The first line contains three integers \(n\), \(m\) and \(len\) \( (1 \le n, m \le \text{constraints},\; 1 \le len \le \ldots)\).

For the next \(n-1\) lines, the \(i\)-th line (for \(i=2,3,\ldots,n\)) contains two integers \(p\) and \(w\), indicating that there is an edge from node \(p\) (the parent) to node \(i\) with initial weight \(w\).

Then, \(m\) lines follow, each representing an operation. Each operation is in one of the following formats:

• 1 x k — a query operation asking for the \(k\)-th smallest depth value in the subtree of node \(x\).
• 2 x k — an update operation. If \(x \neq 1\), add \(k\) to the weight of the edge between \(x\) and its parent; if \(x=1\), add \(k\) to the baseline depth of node 1.

outputFormat

For each query operation, output a single line containing the answer. If the subtree contains fewer than \(k\) nodes, output \(-1\).

sample

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

3
6
11