You are given a grid of integers with r rows and c columns that is sorted so that every row reads left to right in non-decreasing order and every column reads top to bottom in non-decreasing order. Given a target integer, decide whether it appears anywhere in the grid.
The intended solution runs in O(r + c): start at the top-right corner; if the current value equals the target you are done, if it is larger move one step left, and if it is smaller move one step down.
Input format
Line 1: two integers r and c separated by a space.
Next r lines: each contains c space-separated integers, giving the sorted grid row by row.
Final line: a single integer target.
Output format
Print YES if target occurs in the grid, otherwise print NO.
Constraints
- 1 ≤ r ≤ 300
- 1 ≤ c ≤ 300
- -1000000000 ≤ each grid value ≤ 1000000000
- -1000000000 ≤ target ≤ 1000000000
- Each row is non-decreasing left to right and each column is non-decreasing top to bottom.