Joseph loves games about a tree! His friend Nick invented a game for him!

Initially, there is a rooted weighted tree with N vertices numbered $1\dots N$ . Nick guarantees that the tree is connected, and there is a unique path between any vertices! Also he gave us Q queries on it of following type:

• v and k : Let S denote the sorted (non decreasing order) array of shortest distances from v to any other vertex from subtree rooted v. Answer will be $k_{th}$ element of S. If such a number does not exist, i.e. the S has less than k elements, answer is 1. Note that v is not included in his own subtree.

All the indices in the queries are 1-based. Root of the tree is node 1.

But it turns out, Joseph has an exam tomorrow, and he doesn't have time for playing a game! And he asks your help!

Input format

The first line contains a single integer N denoting the number of vertices of the tree.

The next $N - 1$ lines contain three integers $a_i, b_i$ and $w_i$, denoting that there is an edge between vertices $a_i$ and $b_i$ with weight $w_i$.

The next line contains a single integer Q denoting the number of queries.

The next Q lines contain two integers $v_i$ and $k_i$, denoting the query described above.

Output format

Print the answer for each query. Note that if there is no such element, print 1.

Constraints

• $1 ≤ N, Q ≤ 10^5$
• $1 ≤ a_i, b_i, v_i ≤ N; a_i \neq b_i$
• $1 ≤ w_i, k_i ≤ 10^9$

Subtasks

• Subtask #1 (30 points) : $1 ≤ N, Q ≤ 2000$
• Subtask #2 (70 points) : Original constraints