Một con hổ bị lạc trong một khu rừng nguy hiể hình vuông, kích thước N x N mỗi ô địa hình được mã hóa bởi các số 0 hoặc 1. Mỗi lần di chuyển con hổ có thể đi một bước theo 8 hướng xung quanh nó(ưu tiên đi 4 hướng kề nó hơn là các hướng chéo) với điều kiện nó đi sang một ô có cùng tính chất địa hình (giá trị) với ô nó đang đứng. Bạn hãy xem liệu con hổ có thể thoát khỏi khu rừng nguy hiểm này không, nếu có thì mất ít nhất là bao nhiêu bước dịch chuyển con hổ có thể thoát ra được?

Cụ thể phần hướng đi ưu tiên : phải -> dưới -> trái -> trên -> chéo dưới phải -> chéo dưới trái -> chéo trên trái -> chéo trên phải.

Dữ liệu vào:

-Dòng đầu N (2 ≤ n ≤ 150);

-Dòng thứ hai ghi số x, y là giá trị dòng, cột của vị trí đứng ban đầu của con hổ.

-N dòng tiếp theo, mỗi dòng chứa N số (gồm số 0 hoặc số 1) thể hiện cho khu rừng nguy hiểm.

Dữ liệu ra:

-Nếu có được lối ra thì:

+Dòng đầu ghi số 1

+Dòng thứ hai ghi số bước ngắn nhất để con hổ thoát khỏi khu rừng (tại vị trí con hổ đang đứng được tính là 1 bước).

+Các dòng tiếp theo, mỗi dòng ghi một tọa độ nằm trên đường con hổ thoát ra (gồm chỉ số hàng và chỉ số cột, ngăn cách với nhau bởi dấu cách). Đường đi của hổ được xuất phát từ vị trí ban đầu nó đứng.

-Nếu không có lối ra thì ghi ra số 0

Ví dụ 1:

input :

4
2 2
1 0 1 1
1 0 1 1
1 0 0 0
1 1 1 1

output :

1
2
2 2
1 2

Ví dụ 2:

input :

4
2 2
1 1 1 1
1 0 1 1
1 0 0 1
1 1 1 1

output :

0

Ví dụ 3:

input

4
2 2 
1 1 1 1 
1 0 1 1 
1 0 0 1
1 1 0 1

output:

1
3
2 2
3 2
4 3

Giới hạn:

• 25%: 2 <= n <= 10.
• 25%: 10 < n <= 50.
• 50%: không ràng buộc gì thêm.