Existence in Sorted Grid

You are given a grid of integers with dimensions \(n \times m\). Each row and each column in the grid is sorted in non-decreasing order. Your task is to determine whether a given integer \(k\) exists in the grid.

The efficient solution takes advantage of the grid's sorted properties and works in \(O(n+m)\) time by starting at the top-right corner and adjusting the search path accordingly.

Input Constraints: \(1 \leq n, m \leq 10^3\); \(k\) can be any integer.

inputFormat

The first line contains three integers (n), (m), and (k) representing the number of rows, the number of columns, and the target integer respectively. This is followed by (n) lines, each containing (m) space-separated integers denoting the grid.

outputFormat

Print a single line containing "YES" if (k) is found in the grid, or "NO" if it is not.## sample

3 3 5
1 4 7
2 5 8
3 6 9

YES