Đất nước Hẹn hò có \(n\) thành phố được đánh số từ \(1\) đến \(n\) và chúng được kết nối với nhau bởi \(m\) con đường \(2\) chiều (Đảm bảo từ thành phố bất kì đều có thể đi đến thành phố khác bằng \(m\) con đường này). Khoảng cách giữa \(2\) thành phố \((u, v)\) là độ dài tuyến đường ngắn nhất xuất phát từ thành phố \(u\) đi đến thành phố \(v\) qua các con đường.

Hùng sống ở đất nước này và đã có rất người yêu, hiện giờ tất cả đều là người yêu cũ của Hùng. Có \(k\) thành phố được Hùng gọi là đặc biệt vì ở những thành phố này có người yêu cũ của Hùng sống. Hùng gọi độ an toàn của một thành phố là khoảng cách ngắn nhất của thành phố này đến một trong \(k\) thành phố đặc biệt (Vì Hùng sợ người yêu cũ đến làm phiền nên càng xa càng an toàn).

Giả sử Hùng có một kế hoạch đi từ thành phố \(a\) đến thành phố \(b\) thì Hùng cần tìm một con đường đi qua các thành phố sao cho độ an toàn bé nhất trong các thành phố mà Hùng đi qua là lớn nhất

Trong \(q\) ngày tới Hùng quyết định đi dạo khắp đất nước Hẹn hò để đi kiếm thêm người yêu.

Với ngày thứ \(i\) Hùng sẽ đi từ thành phố \(a_{i}\) đến thành phố \(b_{i}\).

Bạn hãy giúp Hùng tính độ an toàn lớn nhất có thể trong các ngày này để Hùng yên tâm đi kiếm người yêu nhé!

Input

• Dòng đầu gồm bốn số nguyên \(n, m, k\) và \(q\) \((1 \leq k \leq n \leq 10^{5}, 1 \leq m \leq 5 \times 10^{5}, 1 \leq q \leq 10^{5})\) lần lượt là số thành phố, số con đường, số thành phố đặc biệt và số ngày Hùng dự định.
• \(m\) dòng tiếp theo gồm ba số nguyên \(u, v\) và \(w\) \((1 \leq u, v \leq n, 1 \leq w \leq 10^{4})\) mô tả một con đường nối hai thành phố \(u\) và \(v\) có độ dài là \(w\).
• Dòng tiếp theo gồm \(k\) số nguyên dương \(x_{1}, x_{2}, \ldots, x_{k}\) \((1 \leq x_{i} \leq n, \forall i \neq j: x_{i} \neq x_{j})\) là số thứ tự của các thành phố đặc biệt.
• \(q\) dòng cuối cùng, mỗi dòng gồm hai số nguyên \(u_{i}, v_{i}\) mô tả truy vấn chuyến đi ngày thứ \(i\) của Hùng \((1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i})\).

Output

• Gồm \(q\) dòng mỗi dòng in ra độ an toàn lớn nhất của \(q\) chuyến đi của Hùng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10, m\leq 50, q \leq 200\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, m, q \leq 1000\) và các truy vấn có \(u_{i}\) kề \(v_{i}\).
• Subtask \(3\) (\(20\%\) số điểm): \(n, m, q \leq 1000\).
• Subtask \(4\) (\(20\%\) số điểm): các truy vấn có \(u_{i}\) kề \(v_{i}\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

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

5
2