Matrix Search in a Sorted Matrix

You are given an N × M matrix in which every row and every column is sorted in increasing order. Your task is to find the position of a given integer x in the matrix. If the integer does not exist in the matrix, output -1 -1.

The search should be performed efficiently. One recommended approach is to start from the top-right corner of the matrix. From there, if the current element is equal to x then you have found its position; if it is greater than x, move left; otherwise, move down.

All indices are 0-indexed.

inputFormat

The input is read from stdin and has the following format:

N M
A[0][0] A[0][1] ... A[0][M-1]
A[1][0] A[1][1] ... A[1][M-1]
...
A[N-1][0] A[N-1][1] ... A[N-1][M-1]
x

Where N and M represent the number of rows and columns of the matrix respectively, each of the next N lines contains M space-separated integers representing the matrix A, and the last line contains the target integer x.

outputFormat

Output the 0-indexed row and column indices of the target integer x separated by a space. If x is not found in the matrix, output -1 -1.

The result should be printed to stdout.

3 4
1 4 7 11
2 5 8 12
3 6 9 16
5

1 1