Description

There is an $m \times n$ grid maze (indicating $m$ rows and $n$ columns), where some cells are passable and others are not. If 1 represents a passable cell and 0 represents an impassable cell, read the $m \times n$ data from the input, along with the starting point and ending point (both described by two values, representing the row number and column number of the point respectively). Your task is to program to find all viable paths under the following rules:

• No repeated points are allowed in the path.

• Movement is restricted to the four directions: up, down, left, right.

If there are no viable paths, output the corresponding information (use $-1$ to indicate no path).

Priority order for movement: up, left, right, down. The data is guaranteed to be randomly generated.

Input Format

The first line contains two integers $m, n$ ($1 < m, n < 15$). Next are $m$ lines of $n$ columns of data consisting of 1s and 0s. The last two lines are the starting point and ending point.

Output Format

All viable paths. Each point is described in the form (x, y). Except for the starting point, all other points are connected using -> to denote the direction.

If there are no viable paths, output $-1$.

Sample Input

5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6

Sample Output

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

Note

The data is guaranteed to be randomly generated. In fact, if $n = m = 14$ and every cell is 1, there are $69450664761521361664274701548907358996488$ paths.