Search in a Sorted Matrix

You are given a matrix of integers with m rows and n columns, where every row is sorted in ascending order from left to right, and every column is sorted in ascending order from top to bottom. Your task is to determine whether a given target integer exists in the matrix.

One efficient solution starts from the top-right corner and eliminates one row or one column at each step based on the comparison with the target.

Your implementation should read input from stdin and write the result to stdout as either 'True' or 'False'.

Note: If the matrix is empty, the output should be 'False'.

inputFormat

The first line contains two space-separated integers, m and n, representing the number of rows and columns respectively. The next m lines each contain n space-separated integers representing the rows of the matrix. The last line contains a single integer, the target value.

outputFormat

Output a single line with 'True' if the target exists in the matrix or 'False' otherwise.## sample

5 5
1 4 7 11 15
2 5 8 12 19
3 6 9 16 22
10 13 14 17 24
18 21 23 26 30
5

True