A tree is a connected graph with no cycles. In this problem, you are given a rooted tree, where each node contains an integer value. And the value of a node is strictly greater than the value of its parent. Now you are given a node and an integer query. You have to find the greatest possible parent of this node (may include the node itself), whose value is greater than or equal to the given query integer.

Input starts with an integer T (≤ 5), denoting the number of test cases.

The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 10⁵), q (1 ≤ q ≤ 50000) where N denotes the number of nodes and q denotes the number of queries. The nodes are numbered from 0 to N-1.

Then there will be N-1 lines. The i^th (1 ≤ i < N) line contains two integers p_i and s_i (0 ≤ p_i < i, 1 ≤ s_i < 2³¹). p_i denotes the parent and s_i denotes the value of the i^th node, respectively. Assume that the given tree is correct and follows the restrictions as stated. You can assume that the 0^th node is the root and its value is 1.

Each of the next q lines contains a query. Each query contains two integers: k and v (1 ≤ k < N, 1 ≤ v ≤ s_k).

For each case, print the case number in a line. Then for each query, print the index of the greatest parent of node k with value greater than or equal to v. You can assume that a solution exists.

Dataset is huge. Use faster I/O methods.