Cho một cây gồm ~n~ đỉnh với các trọng số trên cạnh.

Bạn có ~q~ truy vấn có dạng như sau:

• Nhân thử các cạnh nối với đỉnh ~u_i~ lên ~x_i~ lần, hỏi đường kính của cây mới có độ dài là bao nhiêu.
• Lưu ý là ta chỉ nhân thử, sau truy vấn này thì cây về nguyên bản.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ và ~w~ miêu tả cạnh ~(u,v)~ có độ dài ~w~ của cây.
• Dòng tiếp theo gồm số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng gồm hai số nguyên dương ~u_i,y_i~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra độ dài đường kính của cây mới trong giả định.

Constraints

• ~1 \le n \le 10^5~.
• ~1 \le q \le 10^5~

Subtask

• ~30\%~ số điểm thỏa mãn ~n \le 2000~.
• ~30\%~ số điểm thỏa mãn cây là đường thẳng.
• ~40\%~ số điểm thỏa mãn ~n \le 10^5~

Sample Input 1

8
2 5 3
1 4 2
5 1 2
3 4 1
4 7 2
6 1 6
4 8 2
3
3 2
4 3
1 3

Sample Output 1

11
18
27