Cho đồ thị ~G~ vô hướng, liên thông gồm ~N~ đỉnh (đánh số hiệu từ ~1~ đến ~N~) và ~M~ cạnh (đánh số hiệu từ ~1~ đến ~M~). Giữa hai đỉnh khác nhau của ~G~ có không quá một cạnh nối hai đỉnh đó.

Cho ~K~ là số hiệu của một đỉnh trong đồ thị ~(1 \le K \le N)~. Gọi ~H~ là đồ thị con của đồ thị ~G~. Xét đồ thị con ~H(K)~: ~H(K)~ gồm các đỉnh có số hiệu từ ~1~ đến ~K~ và các cạnh ~(x, y)~ nối hai đỉnh nằm trọn trong khoảng từ ~1~ đến ~K~ ~(1 \le x, y \le K)~.

Yêu cầu: Với mỗi cặp giá trị ~K~ và ~V~ ~(1 \le V \le K \le N)~, liệt kê các đỉnh thuộc vùng liên thông chứa đỉnh ~V~ của đồ thị con ~H(K)~.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~N, M~ ~(1 \le N \le 10^5; 1 \le M \le 2 \cdot 10^5)~ lần lượt là số đỉnh và số cạnh của đồ thị ~G~;

• Dòng thứ hai chứa ~M~ giá trị ~x_i~;

• Dòng thứ ba chứa ~M~ giá trị ~y_i~.

Trong đó: ~(x_i, y_i)~ là cạnh thứ ~i~ ~(1 \le i \le M)~ của đồ thị liên thông ~G~;

• Dòng thứ tư chứa số nguyên dương ~Q~ ~(1 \le Q \le 10^3)~ là số bộ dữ liệu;

• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số ~K, V~ ~(1 \le V \le K \le N)~ lần lượt là số đỉnh của đồ thị con và đỉnh mà vùng liên thông sẽ chứa.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

Gồm ~Q~ dòng, mỗi dòng liệt kê các đỉnh của vùng liên thông chứa đỉnh ~V~ (các đỉnh có thứ tự từ nhỏ đến lớn).

Scoring

Sample Input 1

8 7
1 1 4 4 3 7 5
6 5 1 8 5 3 2
2
4 1
8 3

Sample Output 1

1 4
1 2 3 4 5 6 7 8

Notes

Đồ thị liên thông có ~8~ đỉnh, ~7~ cạnh: ~(1, 6)~, ~(1, 5)~, ~(4, 1)~, ~(4, 8)~, ~(3, 5)~, ~(7, 3)~, ~(5, 2)~. ~Q = 2~ bộ dữ liệu.

Với trường hợp bộ dữ liệu ~1: K = 4, V = 1~, vùng liên thông của đồ thị con chứa đỉnh ~V~ có các đỉnh: ~1, 4~.