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ã số 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, \dots, 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 số ~D~. Chìa khóa 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 có mã khóa là ~2, 4, 6, 8, \dots~, chìa khóa có số ~7~ sẽ mở được các cửa khóa bởi mã khóa là ~7, 14, 21, 28, \dots~. 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, \dots, 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 \le 3 \times 10^5; 1 \le K \le 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 hàng đặ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, \dots, S_K~ (~1 \le S_i \le N; 1 \le i \le K~) mô tả các điểm bán hàng đặc biệt;
• ~M~ dòng, mỗi dòng gồm ba số nguyên ~u, v, c~ (~1 \le u, v \le N; 1 \le c \le 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, 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 1

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 1

2
-1
1
3