Cho một bản đồ là đồ thị vô hướng, liên thông gồm ~n~ đỉnh và ~m~ cạnh. Cạnh nối hai đỉnh ~x,y~ có trọng số ~w~.

Robot sử dụng một loại pin có dung lượng ~p~. Robot chỉ có thể đi qua cạnh có trọng số ~w~ khi lượng pin hiện tại không nhỏ hơn ~w~; sau khi đi qua cạnh, lượng pin bị giảm đi ~w~.

Có ~k~ trạm sạc pin là các đỉnh được đánh số từ ~1~ đến ~k~. Khi robot đến một trạm sạc, pin được sạc đầy trở lại mức ~p~.

Có ~q~ truy vấn dạng ~(x,y)~, trong đó ~x~ và ~y~ đều là các trạm sạc. Với mỗi truy vấn, hãy tìm dung lượng pin nhỏ nhất để robot có thể đi từ ~x~ đến ~y~.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~n,m,k,q~, lần lượt là số đỉnh, số cạnh, số trạm sạc và số truy vấn;

• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~x,y,w~, mô tả một cạnh vô hướng nối ~x~ với ~y~ có trọng số ~w~;

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x,y~ mô tả một truy vấn.

Output

Gồm ~q~ dòng, mỗi dòng chứa dung lượng pin nhỏ nhất cần dùng cho truy vấn tương ứng.

Scoring

Sample Input 1

9 11 3 2
1 3 99
1 4 5
4 5 3
5 6 3
6 4 11
6 7 21
7 2 6
7 8 4
8 9 3
9 2 57
9 3 2
3 1
2 3

Sample Output 1

38
15

Notes

• Với truy vấn thứ nhất, robot có thể đi theo đường:

  ~3 \rightarrow 9 \rightarrow 8 \rightarrow 7 \rightarrow 2 \rightarrow 7 \rightarrow 6 \rightarrow 5 \rightarrow 4 \rightarrow 1~

  bằng loại pin có dung lượng ~38~;

• Với truy vấn thứ hai, robot có thể đi theo đường:

  ~2 \rightarrow 7 \rightarrow 8 \rightarrow 9 \rightarrow 3~

  bằng loại pin có dung lượng ~15~.