Search in a Sorted Matrix

You are given a two-dimensional matrix of integers with dimensions (N \times M). Each row of the matrix is sorted in non-decreasing order from left to right and each column is sorted in non-decreasing order from top to bottom. Your task is to determine whether a given integer (X) is present in the matrix.

The search should be performed efficiently by taking advantage of the sorted properties of the matrix. A common strategy is to start from the top-right corner of the matrix. At any position ((i,j)), if the element is greater than (X), then move left; if it is smaller than (X), then move down; if it is equal, then (X) is found.

For example, consider the matrix:

[ \begin{bmatrix} 1 & 3 & 5 \ 2 & 6 & 8 \ 4 & 7 & 9 \end{bmatrix} ]

Searching for (X = 7) should return true, while (X = 10) should return false.

inputFormat

Input is read from standard input (stdin). The first line contains two integers (N) and (M), representing the number of rows and columns of the matrix respectively. This is followed by (N) lines, each containing (M) space-separated integers representing the rows of the matrix. The last line contains the integer (X) which is to be searched in the matrix.

outputFormat

Output a single line to standard output (stdout) containing either "true" if the integer (X) is found in the matrix or "false" if it is not found.## sample

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

true