Cho một cây có trọng số gồm ~N~ đỉnh và ~N-1~ cạnh. Cạnh thứ ~i~ nối hai đỉnh ~U_i~ và ~V_i~ và có độ dài là ~W_i~.

Cho ~Q~ truy vấn, truy vấn thứ ~i~ có dạng như sau:

• ~X_i~ ~K_i~: Nếu trọng số của tất cả các cạnh có chứa đỉnh ~X_i~ được nhân lên ~K_i~ lần thì đường kính của cây có tổng trọng số là bao nhiêu?

Các truy vấn độc lập, tức là việc thay đổi trọng số của một truy vấn sẽ không ảnh hưởng đến các truy vấn tiếp theo.

Định nghĩa đường kính của cây là đường đi có tổng trọng số lớn nhất của cây.

Input

Dòng đầu tiên là số nguyên dương ~N~ (~2 \le N \le 10^5~) – số đỉnh của cây.

Trong số ~N-1~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên dương ~U_i, V_i~ và ~W_i~ (~1 \le U_i, V_i \le N, 1 \le W_i \le 10^9~), lần lượt là ~2~ đỉnh được nối bởi cạnh và trọng số của cạnh.

Dòng thứ ~N+1~ gồm một số nguyên dương ~Q~ (~1 \le Q \le 10^5~), đại diện cho số truy vấn.

Dòng thứ ~j~ trong số ~Q~ dòng tiếp theo gồm ~2~ số nguyên dương ~X_j~ và ~K_j~ (~1 \le X_j \le N, 1 \le K_j \le 10^9~), là các truy vấn được cho theo mô tả ở trên.

Output

Mỗi dòng trong ~Q~ dòng tiếp theo in ra một số là đáp án của mỗi truy vấn theo mô tả ở trên.

Sample Input 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

Sample Output 1

18
11

Sample Input 2

3
1 2 1000000000
2 3 1000000000
1
2 1000000000

Sample Output 2

2000000000000000000

Notes