Maze Paths Finder

Given an m×n maze where each cell is either walkable (denoted by 1) or blocked (denoted by 0), find all possible paths from a given starting cell to a given destination cell. Both the start and destination are provided as two integers (row and column indices). In each move you may only go one step in one of four directions: left, up, right, or down – and you must not visit any cell more than once in a single path. The order in which you explore the neighbors is fixed: left, then up, then right, then down. If there is no valid path, output -1.


Note: Any formulas must be written in LaTeX. Here the maze size is given as an $m\times n$ grid where $m$ is the number of rows and $n$ is the number of columns.

inputFormat

The input consists of several lines. The first line contains two integers $m$ and $n$, representing the number of rows and columns. The next $m$ lines each contain $n$ integers (either 0 or 1) separated by spaces representing the maze. Then follows a line with two integers indicating the start cell's row and column, and a final line with two integers indicating the destination cell's row and column. All indices are 0-indexed.

outputFormat

If there is at least one valid path, output each path on a separate line. Each path is a sequence of coordinates in the format: (row,col) separated by spaces. If no valid path exists, output a single line with -1.

sample

2 2
1 1
0 1
0 0
1 1

(0,0) (0,1) (1,1)