There is a tree of \(N\) vertices and \(N-1\) edges. The \(i\)-th edge connects vertices \(U_i\) and \(V_i\) and has a length of \(W_i\).
Chaneka, the owner of the tree, asks you \(Q\) times. For the \(j\)-th question, the following is the question format:
- \(X_j\) \(K_j\) – If each edge that contains vertex \(X_j\) has its length multiplied by \(K_j\), what is the diameter of the tree?
Notes:
- Each of Chaneka's question is independent, which means the changes in edge length do not influence the next questions.
- The diameter of a tree is the maximum possible distance between two different vertices in the tree.
Output
Output \(Q\) lines with an integer in each line. The integer in the \(j\)-th line represents the diameter of the tree on the \(j\)-th question.
Note
In the first example, the following is the tree without any changes.
The following is the tree on the \(1\)-st question.
The maximum distance is between vertices \(6\) and \(7\), which is \(6+6+6=18\), so the diameter is \(18\).
The following is the tree on the \(2\)-nd question.
The maximum distance is between vertices \(2\) and \(6\), which is \(3+2+6=11\), so the diameter is \(11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5 1 2
1 4 2
3 4 1
2 5 3
6 1 6
4 7 2
2
4 3
3 2
|
18
11
|
|
2
|
3
1 2 1000000000
2 3 1000000000
1
2 1000000000
|
2000000000000000000
|