Matrix Search Problem

You are given a 2D matrix of integers with m rows and n columns. Each row of the matrix is sorted in ascending order and, similarly, each column is also sorted in ascending order.

Your task is to find a given target integer in the matrix. If the target is found, output its position as a pair of indices (row_index col_index). If the target is not found in the matrix, output "-1 -1".

This problem requires an efficient search algorithm. A common approach is to start from the top-right corner and eliminate either a row or a column in each step. Formally, if we denote the current element as \(A[i][j]\):

• If \(A[i][j] = target\), we return \((i, j)\).
• If \(A[i][j] > target\), we move left (\(j = j - 1\)).
• If \(A[i][j] < target\), we move down (\(i = i + 1\)).

If the search finishes without finding the target, output -1 -1.

inputFormat

The input is read from standard input (stdin) and follows the format below:

Line 1: Two integers m and n, separated by a space, representing the number of rows and columns of the matrix. Next m lines: Each line contains n integers separated by spaces, representing the matrix elements. Last line: A single integer representing the target number to search for.

outputFormat

Print two integers separated by a space: the row index and the column index where the target is found. If the target is not in the matrix, print "-1 -1".## 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

1 1