Vương quốc JOI có \(N\) thành phố được nối với nhau bằng \(M\) con đường hai chiều. Người dân di chuyển giữa các thành phố bằng những con đường này.

Nhiều người dân thích lễ hội, và hiện có \(K\) thành phố đang tổ chức lễ hội rất nhộn nhịp. Tuy nhiên, một số người lại thấy lễ hội ồn ào và muốn tránh đến gần những nơi tổ chức lễ hội nhất có thể. Nhà vua nhờ bạn, một lập trình viên giỏi, viết chương trình trả lời nhanh các câu hỏi về việc di chuyển cho những người này.

Khoảng cách từ một thành phố đến lễ hội là độ dài đường đi ngắn nhất từ thành phố đó đến một thành phố đang tổ chức lễ hội. Khoảng cách đến lễ hội của một lộ trình là giá trị nhỏ nhất trong các khoảng cách đến lễ hội của tất cả thành phố trên lộ trình, bao gồm cả thành phố xuất phát và thành phố đích.

Yêu cầu

Cho thông tin các con đường, các thành phố đang tổ chức lễ hội và \(Q\) truy vấn. Truy vấn thứ \(i\) cho hai thành phố \(S_i,T_i\). Trong tất cả lộ trình từ \(S_i\) đến \(T_i\), hãy tìm khoảng cách đến lễ hội lớn nhất có thể đạt được.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa bốn số nguyên \(N,M,K,Q\). Các thành phố được đánh số từ \(1\) đến \(N\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,L_i\), cho biết con đường hai chiều thứ \(i\) nối hai thành phố \(A_i,B_i\) và có độ dài \(L_i\).
• Trong \(K\) dòng tiếp theo, dòng thứ \(i\) chứa một số nguyên \(F_i\), cho biết thành phố \(F_i\) đang tổ chức lễ hội.
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i,T_i\), là thành phố xuất phát và thành phố đích của truy vấn thứ \(i\).

Các số trên cùng một dòng được phân cách bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(i\) chứa một số nguyên là khoảng cách đến lễ hội lớn nhất trong tất cả lộ trình từ \(S_i\) đến \(T_i\).

Ràng buộc

• \(2\le N\le100\,000\).
• \(1\le M\le200\,000\).
• \(1\le K\le N\).
• \(1\le Q\le100\,000\).
• \(1\le A_i,B_i\le N\) và \(1\le L_i\le1000\) với mọi \(1\le i\le M\).
• Không có đường nối một thành phố với chính nó. Giữa mỗi cặp thành phố có nhiều nhất một con đường.
• Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua các con đường.
• \(1\le F_i\le N\) với mọi \(1\le i\le K\); các giá trị \(F_i\) đôi một khác nhau.
• \(1\le S_i,T_i\le N\) và \(S_i\ne T_i\) với mọi \(1\le i\le Q\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(Q=1\).
• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le5000\) và \(Q\le5000\).

Tổng cộng \(30\%\) số điểm dành cho các dữ liệu thỏa mãn ít nhất một trong hai điều kiện: \(Q=1\); hoặc đồng thời \(N\le5000\) và \(Q\le5000\). Không có dữ liệu chấm nào đồng thời thỏa mãn cả hai điều kiện này.

Ví dụ

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

7
5
0

12 17 2 5
1 3 6
1 6 7
2 3 8
2 4 4
2 8 11
2 12 2
3 6 3
3 7 8
3 11 2
4 12 2
5 10 3
6 10 5
8 9 6
8 12 7
9 10 6
11 9 10
12 9 5
8
7
2 6
5 2
1 10
8 9
9 4

8
8
11
0
6