Barr the bear is training for NAPFA! (yes, even bears have that) In order to ensure that he aces his Standing Broad Jump and 2.4km run, he has decided to get home from school by jumping and walking.

The ground can be represented by a N*N grid, with rows numbered 1 to N from top to bottom and columns numbered 1 to N from left to right. The cell at row r, column c has coordinates (r,c). Barr's home is at (H_r,H_c) and the school is at (S_r,S_c). Barr is initially in school.

Barr can take one giant step to walk up, down, left, or right by one cell. However, certain cells have holes in them, and Barr cannot walk into them. Hence, Barr needs to jump over these holes. Specifically, Barr can only jump over a hole to the top, bottom, left or right of his current cell if the cell after the hole in the corresponding direction is safe. Note that Barr wishes to jump over only holes, and if there aren't any nearby, he has to walk.

	1	2	3	4	5
1	.	.	.	.	.
2	.	.	#	.	.
3	.	#	B	.	.
4	.	.	#	.	.
5	.	.	.	.	.

For example, in the grid above, 'B' represents Barr, '#' represents a hole and '.' represents a free cell. In this case, Barr can jump to (3,1), (1,3) and (5,3) but not to (3,5). Barr can walk right to (3,4) but not to (2,3), (3,2) or (4,3).

Now, Barr wishes to take exactly K steps and jumps in total from school to home to complete his NAPFA training. Help him find an appropriate training route!

Note: Barr can move to any cell more than once, including his home and the school.

Input

On the first line are space-separated integers N and K.

The next line contains space-separated integers S_r, S_c, H_r and H_c.

The next N lines contain N characters each, describing the grid. The j^th character on the i^th of these lines describes the state of the cell with coordinates (i,j). It is either a '.' (for an empty cell) or a '#' (for a cell with a hole).

The input data will guarantee that the school and Barr's home are on different cells, and that there are no holes at the school or Barr's home.

Output

If it is not possible to find a training route with exactly K steps and jumps in total, output on a single line "-1".

Otherwise, the output should contain exactly K lines representing a possible list of moves Barr can take to get from school to home. Line i should contain two space-separated integers Y_i and X_i, indicating that Barr would be at cell (Y_i,X_i) after a jump or a step on the i^th move.

Constraints

For 50% of test data, 1 ≤ N ≤ 100 and 1 ≤ K ≤ 500.

For 100% of test data, 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 100,000, and 1 ≤ S_r, S_c, H_r, H_c ≤ N.

Sample Input 1

3 8
1 1 3 3
.#.
.#.
...

Sample Output 1

1 3
2 3
2 1
1 1
2 1
3 1
3 2
3 3

Explanation for Sample Output 1

1. Jump right from (1,1) to (1,3)
2. Walk down from (1,3) to (2,3)
3. Jump left from (2,3) to (2,1)
4. Walk up from (2,1) to (1,1)
5. Walk down from (1,1) to (2,1)
6. Walk down from (2,1) to (3,1)
7. Walk right from (3,1) to (3,2)
8. Walk right from (3,2) to (3,3)

Sample Input 2

2 2
1 1 2 2
.#
#.

Sample Output 2

-1

Explanation for Sample Output 2