Giải bài trực tuyến

Trong vương quốc C11, ai cũng biết đến biệt đội Lí Lắc (L-TEAM). Đây là tên của đại đội cảnh sát ngầm chủ lực, đặc biệt và duy nhất của vương quốc. L-TEAM được chia thành K tiểu đội Lí Lắc. Vị trí của các tiểu đội trong vương quốc được biểu diễn bằng 1 dãy số bí mật gồm K phần tử S[1], S[2], ..., S[K], với S[i] là tên thành phố mà tiểu đội i đang trú ngụ. Mặc dù rất nổi danh, nhưng hành tung các tiểu đội Lí Lắc được bảo mật rất cẩn thận. Nên không ai biết, ngoại trừ những người trong L-TEAM.

Hôm nay, các bạn sẽ được hé lộ phần nào về phương pháp bảo mật của L-TEAM. Đó chính là "liên tục thay đổi và không bao giờ cố định nơi trú ngụ. Cụ thể hơn, nếu xem vương quốc C11 là một đồ thị vô hướng gồm N đỉnh, M cạnh (Mỗi đỉnh là một thành phố đánh số tự 1 --> N, và mỗi cạnh sẽ cho biết 2 thành phố nằm kề nhau), mỗi tiểu đội sau một ngày bắt buộc phải di chuyển sang một thành phố khác (thành phố đó phải kề và khác với thành phố đang trú ngụ hiện tại). Nên dù hôm nay bạn có biết vị trí trú ngụ của các tiểu đội, thì ngày mai các vị trí đó sẽ tự động trở thành ẩn số.

Quốc vương C11 đang dự tính tổ chức Olympic tin học quốc tế vào một ngày trong tương lai. Ông đã lên một lên danh sách gồm Q câu hỏi thăm dò. Mỗi câu hỏi có dạng (D, E) với ý nghĩa "nếu tổ chức vào ngày thứ D trong tương lai và cần E (cần E đội, nhưng điều dư cũng chẳng sao) tiểu đội để bảo vệ một thành phố thì các thành phố nào có thể được chọn làm nơi tổ chức được ?".

Bạn là lập trình viên giỏi nhất và duy nhất trong L-TEAM. Hôm nay bạn nhận được danh sách thăm dò của quốc vương. Và bạn cũng biết được vị trí hiện tại của các tiểu đội trong ngày hôm nay (tính là ngày thứ 0). Bạn hãy mau trả lời hết các câu hỏi. Nếu không bạn sẽ biết được cơn thịnh nộ của quốc vương là như thế nào !!!.

Input

• Dòng đầu tiên là 4 số nguyên dương N, M, K, Q.
• Dòng thừ hai gồm K số cho biết vị trí của các tiểu đội hiện tại.
• M dòng tiếp theo, mỗi dòng một cặp số nguyên dương (U,V) cho biết 2 thành phố U và V kề nhau.
• Q dòng tiếp theo, mỗi dòng một cặp số nguyên dương (D,E) cho biết câu hỏi của quốc vương.

Output

• Gồm Q dòng, mỗi dòng in ra số lượng thành phố có thể điều E tiểu đội đến để bảo vệ vào ngày thứ D. Biết rằng các tiểu đội không bao giờ giữ nguyên vị trí sau một ngày.

Giới hạn

• 2 ≤ N ≤ 10⁵, M ≤ 2.10⁵, K ≤ 100, Q ≤ 10⁶
• D, E ≤ 10⁹
• 50% số test có N ≤ 100, M ≤ 1000, K ≤ 3, Q ≤ 10⁵
• Đảm bảo đồ thị liên thông

Example

Input:
5 5 3 3
1 2 3
1 2
2 3
3 4
3 5
4 5
3 1
3 2
3 3

Output:
5
4
2

(Trong lúc thi, sẽ chấm trước 4 test (bao gồm test ví dụ)).