Path Finding in a Binary Maze

You are given a maze in the form of an n x m binary grid, where each cell is either 0 (an open cell) or 1 (a blocked cell). The task is to determine whether there exists a path from the top-left cell (1, 1) to the bottom-right cell (n, m). Movement is allowed in four directions: up, down, left, and right.

If a valid path exists, you need to output one such path as a sequence of coordinates using 1-indexed positions. If no path is possible, output -1.

This problem can be solved using a depth-first search (DFS) algorithm with backtracking. Make sure to read the grid from standard input and write your answer to standard output.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) representing the number of rows and columns in the maze respectively. This is followed by n lines, each containing m space-separated integers. Each integer is either 0 (an open cell) or 1 (a blocked cell).

outputFormat

If a valid path exists, output the path by printing each 1-indexed coordinate pair on a new line, starting from (1, 1) and ending at (n, m). If there is no valid path, output a single line containing -1.

## sample

4 4
0 1 0 0
0 1 0 1
0 0 0 0
1 1 1 0

1 1
2 1
3 1
3 2
3 3
3 4
4 4

</p>