You will be given a binary tree with N nodes (1 <= N <= 100000) numbered from 0 to N - 1, each one labeled with some integer. You have to answer Q (1 <= Q <= 75000) queries, each one denoted by some node (some integer between 0 and N 1). The answer for each query is the largest difference of the labels you find in the path from the given node to the root of the tree, which will always be node 0. N will be given in the first line of the input. N lines follow, the i-th line describes the data of the i-th node of the tree (first line describes node 0, and so on), with 3 integers: label, left child, right child. The absence of any of the children will be denoted by -1. Then a line with the integer Q, followed by Q lines, each one a single query as described above.

Case 1: For the input provided as follows: 3

10 1 2

12 -1 -1

15 -1 -1

2

1

2

Output of the program will be:

2

5

Case 2:

For the input provided as follows:

3

10 1 -1

15 2 -1

20 -1 -1

2

1

2

Output of the program will be:

5

10