Prepare for ACTVN ACM/ICPC 2020 Contest

Đôi bạn thân Tí và Tèo đang cùng nhau học chơi Cờ vua, Tí nhận thấy quân Mã trong cờ vua rất thú vị. Vì nó không bị chặn bởi những quân cờ khác mà những bước di chuyển của nó còn đa dạng và khó đoán.

Cùng lúc này, Tèo nghĩ ra câu hỏi nếu trên bàn cờ có nhiều hơn 4 quân mã thì với thế cờ hiện tại trên bàn cờ, quân mã nào sẽ ăn được nhiều quân cờ nhất có thể.

Bài toán đặt ra là có rất nhiều quân mã trên bàn cờ, trên đó còn những quân cờ mà quân mã được phép ăn cũng như không được phép ăn. Tèo muốn biết quân mã nào ăn được nhiều quân cờ nhất trên bàn cờ nên 

đã đưa bài toán này cho Tí.

Để không mất thời gian kiểm tra lại kết quả của Tí đưa ra, cũng như Tèo sợ Tí chơi ăn gian (đoán mò) nên muốn viết một chương trình để tính toán kết quả của bài toán trên.

Các bạn hãy cùng Tèo viết chương trình này các bạn nhé.

Input

Dòng đầu tiên là số testcase T của bài toán ( 1 <= T <= 100)

Mỗi testcase được cho trên 4 dòng, với các thông tin sau:

 - Dòng đầu tiên chứa: kích thước bàn cờ N (8 <= N <= 1000), số quân mã hiện có trên bàn cờ K ( 4 <= K <= N*N-1 ), số quân cờ còn lại trên bàn cờ M ( 1 <= M <= N*N-K), số quân cờ không được phép ăn D ( 1 <= D <= M)

 - Dòng tiếp theo chứa 2*K số nguyên (x, y) cho biết vị trí của quân mã trên bàn cờ (0 <= x, y < N)

 - Dòng tiếp theo chứa 2*M số nguyên (x, y) cho biết vị trí của những quân cờ còn lại trên bàn cờ (0 <= x, y < N)

 - Dòng cuối cùng chứa 2* D số nguyên (x, y) cho biết vị trí của những quân cờ không được phéo ăn trên bàn cờ (0 <= x, y < N)

Dữ liệu đảm bảo không có 2 quân cờ nào trùng nhau, những vị tri quân cờ không được phép ăn đã tồn tại trong bàn cờ.

Output

Mỗi test case được in ra trên một dòng, với:

Bắt đầu bằng ký tự "#", tiếp theo là số thứ tự của testcase đó, tiếp đến là 1 khoảng trắng (dấu cách), tiếp theo là 2 số x, y cho biết vị trí của quân mã ăn được nhiều quân cờ còn lại nhất, tiếp đến là 1 khoảng trắng, và cuối cùng là số quân cờ mà quân mã này đã ăn. Nếu có nhiều hơn 1 quân mã ăn được nhiều quân cờ còn lại nhất, thì in ra quân mã đầu tiên trong dãy các quân mã nhập vào.

(Chi tiết xem thêm tại example output)

Example

Input:
1
4 3 10 1
3 1 3 3 3 0
2 1 2 0 1 2 2 2 1 1 1 3 3 2 0 2 2 3 0 3
3 2

Output:
#1 3 1 2