COETEST5

Output

Đưa ra output trên T dòng tương ứng với T test case.

Mỗi test case in ra "#tc", với tc là số thứ tự của test case, đánh số bắt đầu từ 1, tiếp theo là một dấu cách và kết quả tương ứng của test case đó.

Kết quả in ra gồm 3 trường hợp sau:

- Nếu không cần đặt thêm chướng ngại vật thì in ra 0.

- Nếu không thể áp dụng ý tưởng đã mô tả để giúp robot tới được đích thì in ra -1.

- Nếu áp dụng ý tưởng đã mô tả ở trên thành công để giúp robot tới được đích, thì in ra toạ độ hàng và cột cách nhau bởi một dấu cách của vị trí đặt thêm vật cản.

Chú ý: Trường hợp có nhiều vị trí áp dụng được ý tưởng thì in ra toạ độ hàng nhỏ hơn. Nếu cùng hàng thì in ra vi trí có cột nhỏ hơn.

Example

Input:
5
5
5
0 0 1 0 0 
0 0 0 3 0 
0 2 0 0 0 
0 0 1 0 0 
0 0 0 0 0 
9
3 2 4 1 1 2 2 1 3 
7
0 0 0 0 0 0 1 
0 0 0 0 0 0 0 
0 0 1 0 0 0 0 
0 0 0 0 1 1 0 
0 0 2 0 0 0 0 
0 0 0 0 1 0 0 
0 3 0 0 0 0 1 
20
1 2 1 1 2 3 1 4 2 3 4 4 1 3 2 3 3 3 4 4 
8
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
1 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 2 
0 3 1 0 1 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
25
1 4 1 4 4 4 3 4 3 4 2 2 1 2 3 2 1 3 1 4 1 4 4 4 1 
11
0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 2 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 1 1 0 
0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 0 1 0 0 1 1 
0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 3 0 0 0 0 0 0 
36
3 1 3 2 3 3 3 2 1 1 1 2 1 2 3 1 2 2 2 2 4 3 2 4 4 3 4 3 3 3 3 4 4 3 3 4 
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 
0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 
0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 3 2 1 0 0 0 0 
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
37
3 2 3 2 1 2 3 3 3 3 3 2 4 3 1 4 4 1 2 4 4 4 4 4 4 1 2 1 1 1 1 2 2 2 2 2 2

Output:
#1 4 1
#2 2 4
#3 3 8
#4 5 8
#5 10 12