SOLVE
LATER
Little Santa have to give gifts to N children. There are \(N-1\) roads connecting the homes of N children. Each road has some special Santa tax value which only Santa have to pay. Little Santa is wondering what is the \(realK^{th}\) minimum tax value in the path between the home of child \(realA\) and child \(realB\).
Note: \(k^{th}\) minimum value in a list A is \(k^{th}\) value in the list A after sorting A.
Input format:
First line contains one integer, N \((2 \leq N \leq 7.5 * 10^5)\), denoting the number of children. Next \(N-1\) lines contains three space separated integers each, \(x, y, w\) \((1 \le x, y \le N), (0 \le w \le 10^9)\), denoting that home of child x is connected to home of child y and the tax value of the road is w. Next line will contain an integer, q \((1 \le q \le 7.5*10^5)\), denoting the number of queries. Next q lines contains three space separated integers each, \(a, b\) \((1 \le a, b \le N)\) and k \((1 \le k \le N-1)\).
To generate \(realA\) and \(realB\) you have to use following formulas:
Where \(lastAns\) is answer for previous query, or 0 if this is the first query.
Output format:
For each query, print the number the \(realK^{th}\) minimum tax value in the path between the home of child \(realA\) and child \(realB\). Print 1 if there is no such value.
Here are the real values for queries from sample:
\(realA_1 = 4, realB_1 = 5, realK_1 = 1\)
\(realA_2 = 3, realB_4 = 4, realK_2 = 1\)
\(realA_3 = 5, realB_3 = 2, realK_3 = 1\)