Parking Lot

A square parking lot has size N by N. Many cars are parked in it, and car 1 is our car. A parking attendant can move only one car at a time. We call one action of getting into a car and moving that car one operation.

During one operation, the selected car may move any positive number of cells forward or backward along its fixed orientation, as long as it does not overlap another car. Compute a sequence of cars to move that gets car 1 out of the parking lot using the minimum possible number of operations. If several minimum sequences exist, output any one of them.

Assumptions

1. Every car has width 1 and length 2 or 3.
2. A vertical car can move only up and down, and a horizontal car can move only left and right. Cars cannot rotate.
3. The same car may be moved in more than one operation.
4. No car except car 1 may leave the parking lot at any point. The whole process ends as soon as car 1 is completely outside the parking lot.
5. If car 1 is horizontal, it can leave only to the right. If car 1 is vertical, it can leave only upward.
6. The input is guaranteed to describe a parking lot from which car 1 can leave.

Figure 1. Initial parking lot

Figure 2. Parking lot after car 1 has left

The first line contains an integer N (3 <= N <= 15), the size of the parking lot.

Each of the next N lines contains N integers separated by spaces. A 0 means an empty cell, 1 means our car, and the other cars are numbered consecutively starting from 2.

Print an integer K on the first line, the total number of operations.

Then print K lines in the order the operations are performed. Each line contains two integers. The first integer is the number of the car being moved, and the second integer is the distance moved, measured in grid cells.

For a horizontal car, a move to the right is positive and a move to the left is negative. For a vertical car, a move upward is positive and a move downward is negative.