Tại Việt Nam, VinFast là đơn vị tiên phong trong sản xuất xe điện và thử nghiệm các hệ thống tự động. Công ty đã xây dựng được một hệ thống các trạm xạc điện phủ khắp cả nước. Hệ thống trạm xạc được mô hình hóa thành một đơn đồ thị vô hướng liên thông có trọng số gồm ~n~ đỉnh (là các trạm xạc được đánh số từ ~1~ đến ~n~), ~m~ cạnh và trọng số ~w_{u,v}~ là khoảng cách giữa trạm xạc ~u~ đến trạm xạc ~v~ ~(1 \le u, v \le n)~. Công ty đang thử nghiệm hệ thống tự động xạc nhanh cho các xe điện gồm có ~k~ trung tâm năng lượng được đặt tại các đỉnh từ ~1~ đến ~k~. Một xe điện đang có mức năng lượng ~x~ chỉ có thể di chuyển từ trạm xạc ~u~ đến trạm xạc ~v~ nếu ~x \ge w_{u,v}~ và sẽ mất ~w_{u,v}~ năng lượng. Quá trình thử nghiệm, công ty đặt các Power Recharge Object (PRO) tại các trung tâm năng lượng với mức năng lượng ~c~ cho tất cả các PRO. Khi một xe điện đi qua một PRO, năng lượng của xe sẽ được nạp lại đúng bằng ~c~.

Yêu cầu: Bản kế hoạch có ~q~ lần thử nghiệm, lần thứ ~i~ cho xe điện di chuyển từ đỉnh ~a_i~ đến đỉnh ~b_i~. Chi phí duy trì các PRO có mức năng lượng càng cao thì càng đắt, nên với mỗi lần thử nghiệm, công ty cần tính toán mức năng lượng thấp nhất cần thiết lập cho các PRO sao cho xe có thể di chuyển từ đỉnh ~a_i~ đến đỉnh ~b_i~.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~n, m, k, q~ ~(1 \le n, m, q \le 10^5; 1 \le k \le n)~;

• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~v_i, u_i, w_i~ biểu diễn cạnh nối giữa hai đỉnh ~v_i~ với ~u_i~ có trọng số ~w_i~ ~(1 \le v_i, u_i \le n, v_i \ne u_i, w_i \le 10^9)~;

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a_i, b_i~ ~(1 \le a_i, b_i \le k, a_i \ne b_i)~.

Đồ thị đảm bảo là đơn đồ thị liên thông.

Output

Gồm ~q~ dòng, dòng thứ ~i~ tương ứng là mức năng lượng thấp nhất cần thiết lập cho các PRO đối với lần thử nghiệm thứ ~i~ ~(1 \le i \le q)~.

Scoring

Sample Input 1

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

Sample Output 1

6

Notes

Ví dụ một hành trình di chuyển thỏa mãn là: ~2 \rightarrow 1 \rightarrow 4 \rightarrow 3~.

Từ trạm xạc xuất phát ~2~ nạp mức năng lượng ~6~, đến trạm xạc ~1~ tự động nạp lại mức năng lượng ~6~, di chuyển tiếp đến trạm xạc ~4~ mức năng lượng còn ~2~, tiếp tục di chuyển đến trạm xạc ~3~.