Thẳng tham gia thử thách "check-in" trong hội chợ tết của thành phố. Hội chợ gồm có ~N~ điểm bán hàng được đánh số từ ~1~ đến ~N~. Các điểm bán hàng được nối với nhau bởi ~M~ đường hai chiều, mỗi đường có một cửa chắn với mã khóa là một số nguyên dương. Các mã khóa trên cửa chắn là đôi một khác nhau. Có ~K~ điểm bán hàng đặc biệt ~S_1, S_2, ..., S_K~ là điểm "check-in" để hoàn thành thử thách.

Ở mỗi lượt, ban đầu cửa chắn tại tất cả các con đường đều khóa. Người chơi sẽ nhận được thông tin gồm hai số tự nhiên ~X~ và ~D~ tương ứng là số hiệu của điểm bán hàng xuất phát và chìa khóa có số ~D~.

Chìa khóa có số ~D~ sẽ mở được những cánh cửa có mã khóa là bội của ~D~. Ví dụ: chìa khóa có số ~2~ sẽ mở được các cánh cửa bị khóa bởi mã khóa là ~2~, ~4~, ~6~, ~8~, ...; chìa có số ~7~ sẽ mở được các cửa bị khóa bởi mã khóa là ~7, 14, 21, 28~, ... Người chơi cần tìm đường đi như sau:

• Xuất phát từ điểm bán hàng ~X~.
• Đích đến là một trong các điểm bán hàng đặc biệt ~S_1, S_2, ..., S_K~.
• Số lượng con đường đi qua là nhỏ nhất.

Yêu cầu: Thắng tham gia ~Q~ lượt chơi, với mỗi lượt Thắng nhận được một cặp số (~X~, ~D~). Em hãy lập trình đưa ra số lượng con đường nhỏ nhất Thắng cần đi qua để đến đích tại mỗi lượt chơi.

INPUT

• Dòng đầu tiên gồm bốn số nguyên dương ~N, M, K, Q~ (~N, M, Q ≤ 3 \times 10^5~, ~1 ≤ K ≤ N~) tương ứng lần lượt là số lượng điểm bán hàng, sô lượng con đường nối giữa ~N~ điểm bán, số lượng điêm bán đặc biệt và số lượt chơi.
• Dòng thứ hai gồm ~K~ số nguyên dương ~S_1, S_2, ..., S_k~ (~1 ≤ S_i ≤ N~, ~1 ≤ i ≤ K~) mô tả các điểm bán hàng đặc biệt.
• ~M~ dòng sau, mỗi dòng gồm ba số nguyên ~u, v, c~ (~1 ≤ u, v ≤ N~, ~1 ≤ c ≤ 10^6~) mô tả có một đường hai chiều nối giữa điểm bán ~u~ và điểm bán ~v~ mà trên đường đó có một cánh cửa chắn với mã khóa là ~c~.
• ~Q~ dòng sau, mỗi dòng gồm hai số nguyên ~X~ và ~D~ là thông tin của mỗi lượt chơi.

OUTPUT

Gồm ~Q~ dòng, tương ứng với ~Q~ lượt chơi, nêu có đường đi thỏa mãn yêu cầu đề bài thì in ra số con đường nhỏ nhất Thắng cần đi qua để đến đích, ngược lại, nếu không có cách nào để đi đến đích thì in ra ~-1~.

SAMPLE INPUT

5 7 2 4
4 5
3 4 14
1 2 16
2 4 5
1 4 7
4 5 9
1 3 8
3 5 4
1 2
1 5
1 1
2 4

SAMPLE OUTPUT

2
-1
1
3

• Ở lượt chơi ~1~, có thể chọn đường đi: ~1 → 3 → 5~ hoặc ~1 → 3 → 4~ đều có số lượng con đường đi qua nhỏ nhất là ~2~.
• Ở lượt chơi ~2~, không có đường đi thỏả mãn.
• Ở lượt chơi ~3~, có thể chọn đường đi: ~1 → 4~.
• Ở lượt chơi ~4~, có thể chọn đường đi: ~2 → 1 → 3 → 5~.

SUBTASKS

• ~30 \%~ số test có ~Q = 1~, ~D = 1~.
• ~15 \%~ số test có ~K = 1~, ~D \le 10~.
• ~25 \%~ số test có ~D \le 10~.
• ~20 \%~ số test có ~D \le 10^4~.
• ~10 \%~ số test không có ràng buộc gì thêm.