Matrix Target Search

You are given an ( m \times n ) matrix of integers where each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom. Your task is to determine whether a given integer target exists in the matrix. If the target exists, print True; otherwise, print False.

For example, consider the matrix below:

[ \begin{bmatrix} 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 \end{bmatrix} ]

If the target is (5), the answer is True; if the target is (20), the answer is False.

You need to implement a solution that reads from standard input and writes to standard output.

inputFormat

The input is given in the following format via standard input:

• The first line contains two integers (m) and (n), indicating the number of rows and columns of the matrix respectively.
• The next (m) lines each contain (n) space-separated integers representing the matrix rows.
• The final line contains an integer, the target value.

For example:

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

outputFormat

Output a single line to standard output containing either True if the target is found 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