주차장

정사각형 N x N 크기의 주차장이 있다. 주차장에는 여러 대의 차가 있고, 1번 차가 우리가 빼내야 하는 차이다. 차를 움직일 수 있는 주차관리원은 한 명뿐이다. 주차관리원이 어떤 차에 타서 그 차를 움직이는 일을 한 번의 작업이라고 한다.

한 번의 작업에서 선택한 차는 자신의 방향을 따라 앞이나 뒤로 1칸 이상 움직일 수 있다. 단, 움직이는 동안 다른 차와 겹치면 안 된다. 1번 차를 주차장 밖으로 빼내기 위해 필요한 작업 횟수를 최소로 하면서, 어떤 차들을 어떤 순서로 움직일지 구하는 프로그램을 작성하시오. 가능한 정답이 여러 가지라면 그중 하나만 출력해도 된다.

가정

1. 모든 차의 폭은 1이고, 길이는 2 또는 3이다.
2. 수직으로 놓인 차는 위아래로만, 수평으로 놓인 차는 좌우로만 움직일 수 있다. 차는 회전할 수 없다.
3. 같은 차를 여러 번 작업할 수 있다.
4. 1번 차를 제외한 다른 차는 작업 도중 주차장 밖으로 조금이라도 나갈 수 없다. 1번 차가 완전히 주차장 밖으로 나가는 순간 전체 작업은 끝난다.
5. 1번 차가 수평차라면 오른쪽으로만, 수직차라면 위쪽으로만 주차장 밖으로 나갈 수 있다.
6. 입력으로 주어지는 주차장은 1번 차가 반드시 빠져나갈 수 있다.

그림 1. 초기 주차장의 모습

그림 2. 1번 차를 빼낸 뒤의 주차장 모습

첫째 줄에 주차장의 크기 N (3 <= N <= 15)이 주어진다.

다음 N개 줄에는 각각 N개의 정수가 공백으로 구분되어 주어진다. 0은 빈 칸, 1은 우리가 빼내야 하는 차를 뜻한다. 나머지 차에는 2부터 시작하는 연속된 번호가 붙어 있다.

첫째 줄에 전체 작업 횟수 K를 출력한다.

다음 K개 줄에는 수행한 작업을 순서대로 출력한다. 각 줄에는 정수 두 개를 출력한다. 첫 번째 정수는 움직인 차의 번호이고, 두 번째 정수는 움직인 거리이다. 거리는 격자의 칸 수로 나타낸다.

수평차는 오른쪽으로 움직인 거리를 양의 정수, 왼쪽으로 움직인 거리를 음의 정수로 나타낸다. 수직차는 위쪽으로 움직인 거리를 양의 정수, 아래쪽으로 움직인 거리를 음의 정수로 나타낸다.