Safe Path in a Grid

You are given a grid with m rows and n columns, where each cell is either safe (denoted by 0) or blocked (denoted by 1). Starting from the top-left corner of the grid, you need to determine whether there is a safe path to the bottom-right corner. You can only move in two directions: right (i.e., from cell (i, j) to cell (i, j+1)) and down (i.e., from cell (i, j) to cell (i+1, j)).

Note:

• The starting cell and the destination cell must be safe.
• If no safe path exists, output false.

The existence of a safe path is defined mathematically as follows:

$$\text{Answer} = \begin{cases} \texttt{true}, & \text{if } \exists \; \text{a sequence } (i_0, j_0), (i_1, j_1), \ldots, (i_k, j_k) \\ & \quad \text{with } (i_0, j_0) = (0,0),\ (i_k, j_k) = (m-1, n-1), \\ & \quad \text{and } (i_{t+1}, j_{t+1}) - (i_t, j_t) \in \{(0,1), (1,0)\} \text{ for } 0 \le t < k, \\ \texttt{false}, & \text{otherwise.} \end{cases} $$

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two integers m and n separated by a space, representing the number of rows and columns respectively.
2. The next m lines each contain n space-separated integers (each either 0 or 1) representing the grid.

outputFormat

Output to standard output (stdout) a single line containing true if there exists a safe path from the top-left to the bottom-right corner, and false otherwise.

## sample

4 5
0 0 1 0 1
0 1 0 0 0
0 0 0 1 0
1 1 0 0 0

true