The goal of this puzzle is to indicate the less dangerous way for a special ops to accomplish his mission. Basically the mission we are concerned about is traveling from one point to another in the least time, without being killed.

The problem is modeled as a NxM grid where each cell has a cost: the time required to cross it.
In addition, there are enemies which can either be avoided or killed. Each enemy covers a 3x3 square composed of the cell on which he is standing and all the cells around it.

Last, you have gun with a limited number of bullets. One bullet kills one enemy, you're not forced to use them all, or even to use any of them if your cherish human life too much.

Input Specifications

Your program must take one and only one command line argument: the input file.
The input file is formatted as follows:

1. the first line contains 4 integers n m e b where
   
   • n is the number of rows of the grid
   • m is the number of columns of the grid
   • e is the number of enemies on the grid
   • b is the number of bullets available to you
2. the second line contains 4 integers start_r start_c stop_r stop_c where
   
   • start_r,start_c are the coordinates of the row and column where your start
   • stop_r,stop_c are the coordinates of the row and column of the destination to reach
3. the n following lines represent one row of the grid (from row 0 to row n-1), each row is composed of m space separated integers
4. the e following lines represents the enemies positions row column

Example:

5 5 1 1
0 0 3 4
3 5 8 1 5
7 1 1 7 6
5 3 2 7 7
2 8 7 1 8
3 5 4 3 2
2 2

The grid is of size 5x5, there's 1 enemy and you have one bullet.
You start from position (0,0) and must reach position (3,4), remember that positions are (row,column).

Output Specifications

You must print your output to the standard output (printf, etc...).
The output should be formatted as follows:

1. the first line contains k l where
   
   • k is the number of enemies you killed
   • l is the length of the path you traveled
2. the k following lines contain the location of the killed enemies row column
3. the l following lines contain the positions row column you traversed on the path from start to stop

Scoring

The lesser the cost of path the more points your solution is awarded. The points are summed over all test cases.

Example outputs

For the previous example one possible solution is:

0 10
0 0
1 0
2 0
3 0
4 0
4 1
4 2
4 3
4 4
3 4

In this solution no enemy was killed, and the path contained 10 positions. The total cost is 42. It can be computed by summing up the costs of the grid cells. This task is performed by our checker in order to score to your solution.

Another possible solution, this time killing an enemy:

1 8
2 2
0 0
0 1
1 1
1 2
2 2
2 3
3 3
3 4

So here you killed 1 enemy, that path contained 8 positions. The enemy killed was at position (2,2). The total cost is 28. This solution is significantly better than the previous one and would give you a much higher score.