Mô tả vấn đề

Bạn được cho một cây với ~N~ đỉnh.
Biết rằng, cây là một dạng đồ thị, và cụ thể hơn là một đồ thị vô hướng được kết nối với ~N-1~ cạnh, với ~N~ là số đỉnh của cây.
Cạnh thứ ~i~-th ~(1≤i≤N-1)~ được kết nối với đỉnh ~a_i~ và ~b_i~ , và có độ dài cạnh là ~c_i~ .

Bạn được cung cấp ~Q~ truy vấn và số nguyên ~K~ .Ở truy vấn thứ ~j~ -th ~(1≤j≤Q)~ :

• Hãy tìm khoảng cách ngắn nhất đi từ đỉnh ~x_j~ qua ~y_j~ và đi qua đỉnh ~K~ .

Mô tả đầu vào

• ~3≤N≤10^5~
• ~1≤a_i,b_i≤N (1≤i≤N-1)~
• ~1≤c_i≤10^9 (1≤i≤N-1)~
• The given graph is a tree.
• ~1≤Q≤10^5~
• ~1≤K≤N~
• ~1≤x_j,y_j≤N (1≤j≤Q)~
• ~x_j≠y_j (1≤j≤Q)~
• ~x_j≠K,y_j≠K (1≤j≤Q)~

Input

~N~

~a_1~ ~b_1~ ~c_1~

~:~

~a_{N-1}~ ~b_{N-1}~ ~c_{N-1}~

~Q~ ~K~

~x_1~ ~y_1~

~:~

~x_{Q}~ ~y_{Q}~

Output

In ra ~Q~ dòng.
Với dòng thứ ~j~th ~j(1≤j≤Q)~ ,in ra khoảng cách ngắn nhất theo yêu cầu.

Sample Input 1

5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

Sample Output 1

3
2
4

Các đường dẫn ngắn nhất cho ba truy vấn như sau:

• Truy vấn ~1~ : Đỉnh ~2~ → Đỉnh ~1~ → Đỉnh ~2~ → Đỉnh ~4~ : Khoảng cách ~1+1+1=3~
• Truy vấn ~2~ : Đỉnh ~2~ → Đỉnh ~1~ → Đỉnh ~3~ : Khoảng cách ~1+1=2~
• truy vấn ~3~ : Đỉnh ~4~ → Đỉnh ~2~ → Đỉnh ~1~ → Đỉnh ~3~ → Đỉnh ~5~ : Khoảng cách ~1+1+1+1=4~

Sample Input 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

Sample Output 2

5
14
22

Sample Input 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

Sample Output 3

17000000000