Valid Path in a Grid

Given a grid of dimensions \(N \times M\) consisting of only 0s and 1s, determine if there exists a valid path from the top-left cell to the bottom-right cell. A cell with a value of 1 is traversable, while 0 is blocked. You can only move in one of the following three directions: right, down, or diagonally down-right.

The task is to print YES if such a path exists, otherwise print NO. The moves are allowed only if the destination cell is a 1. This problem can be solved using a breadth-first search (BFS) algorithm.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (N) and (M) separated by a space. Each of the following (N) lines contains (M) integers (either 0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single line to standard output (stdout) with the word YES if there exists a valid path from the top-left to the bottom-right corner, or NO if no such path exists.## sample

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

YES