Hội khỏe Phù Đổng tổ chức vào ngày 24 tháng 3 để tiến tới tổ chức chào mừng ngày thành lập Đoàn, có n đoàn (sinh viên và khách mời) được đánh số từ 1 đến n, từ các tỉnh thành trên cả nước tập trung tổ chức hội trại giao lưu thể thao ca nhạc. Khu vực hội trại có n trại được đánh số từ 1 đến n. Đoàn thứ i đươc phân vào trại i. Sơ đồ giao thông của khu vực hội trại gồm m đoạn đường hai chiều, mỗi đoạn đường nối trực tiếp hai trại khác nhau. Sơ đồ giao thông đảm bảo là giữa hai trại bất kỳ luôn có đường đi nối chúng. Trong số các trại này có p trại khách mời (y1, y2,…, yp), các trại này cần được giữ yên tĩnh. Giữa các trại tổ chức các hoạt động giao lưu diễu hành. Hai trại u và v giao lưu bằng cách đi diễu hành từ trại u sang trại v thông qua đường đi trực tiếp nếu có hoặc đi qua một dãy các trại trung gian, ở mỗi trại tổ chức đánh trống, thổi kèn, nhảy múa, hát hò ầm ĩ. Để giữ sự yên tĩnh cho các trại khách mời nên đoàn diễu hành cần chọn đường đi giảm gây ồn nhiều nhất cho các trại khách mời.
Giả sử L(u,v)=(x1, x2,…, xk), trong đó u=x1, v=xk và có đoạn đường nối xi với xi+1 với mọi i = 1, 2, ..., k–1, là một hành trình của đoàn diễu hành từ trại u đến trại v, Ban tổ chức hội trại định nghĩa độ giảm thanh của hành trình L(u,v) là
,
với D(xi, yj) là độ dài đường đi ngắn nhất giữa hai trại xi và yj.
Yêu cầu: Với hai trại u và v hãy tìm hành trình có độ giảm thanh lớn nhất.
Hội khỏe Phù Đổng tổ chức vào ngày 24 tháng 3 để tiến tới tổ chức chào mừng ngày thành lập Đoàn, có n đoàn (sinh viên và khách mời) được đánh số từ 1 đến n, từ các tỉnh thành trên cả nước tập trung tổ chức hội trại giao lưu thể thao ca nhạc. Khu vực hội trại có n trại được đánh số từ 1 đến n. Đoàn thứ i đươc phân vào trại i. Sơ đồ giao thông của khu vực hội trại gồm m đoạn đường hai chiều, mỗi đoạn đường nối trực tiếp hai trại khác nhau. Sơ đồ giao thông đảm bảo là giữa hai trại bất kỳ luôn có đường đi nối chúng. Trong số các trại này có p trại khách mời (y1, y2,…, yp), các trại này cần được giữ yên tĩnh. Giữa các trại tổ chức các hoạt động giao lưu diễu hành. Hai trại u và v giao lưu bằng cách đi diễu hành từ trại u sang trại v thông qua đường đi trực tiếp nếu có hoặc đi qua một dãy các trại trung gian, ở mỗi trại tổ chức đánh trống, thổi kèn, nhảy múa, hát hò ầm ĩ. Để giữ sự yên tĩnh cho các trại khách mời nên đoàn diễu hành cần chọn đường đi giảm gây ồn nhiều nhất cho các trại khách mời.
Giả sử L(u,v)=(x1, x2,…, xk), trong đó u=x1, v=xk và có đoạn đường nối xi với xi+1 với mọi i = 1, 2, ..., k–1, là một hành trình của đoàn diễu hành từ trại u đến trại v, Ban tổ chức hội trại định nghĩa độ giảm thanh của hành trình L(u,v) là
min {D(xi, yj)} với i = 1..k và j = 1..p
với D(xi, yj) là độ dài đường đi ngắn nhất giữa hai trại xi và yj.
Yêu cầu: Với hai trại u và v hãy tìm hành trình có độ giảm thanh lớn nhất.
Input
• Dòng đầu chứa bốn số nguyên dương n, m, p, q (n ≤ 10^5, m ≤ 2×10^5, q ≤ 10^5), trong đó n là số lượng trại, m là số lượng đoạn đường, p là số lượng trại khách mời (p ≤ n) và q là số lượng truy vấn;
• Mỗi dòng trong số m dòng tiếp theo là thông tin về một đoạn đường gồm ba số nguyên dương u, v, l (u, v ≤ n; l ≤ 1000), cho biết hai trại u và v được nối trực tiếp bởi đoạn đường có độ dài l;
• Dòng tiếp theo chứa p số nguyên dương là các chỉ số của các trại khách mời;
• Mỗi dòng trong q dòng tiếp theo gồm hai số nguyên dương u và v đòi hỏi trả lời truy vấn: “Tìm hành trình từ trại u đến trại v có độ giảm thanh lớn nhất”.
Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.
Output
Gồm q dòng: Dòng thứ i ghi một số nguyên dương là độ giảm thanh lớn nhất tìm được đối với truy vấn thứ i.
Example
Input:
6 7 2 2
1 3 2
2 3 6
2 4 1
3 4 2
3 5 4
5 4 5
4 6 3
1 6
2 5
6 3
Output:
3
0
Hình vẽ minh họa cho ví dụ:
