Search in Sorted Matrix

Given an \( n \times n \) matrix in which every row and every column is sorted in ascending order, your task is to search for a given target element. If the element exists in the matrix, output its position as a pair of 0-indexed integers \( (row, col) \); otherwise, output -1.

Example:

Input:
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
Output:
1 1

</p>

The matrix provided is sorted such that for every element \( a_{ij} \) in the matrix, all elements to its right and below are greater or equal, which allows an efficient search algorithm. Consider using the "staircase" search approach for an optimal solution.

inputFormat

The input is read from standard input (stdin) in the following format:

• The first line contains an integer \( n \), representing the dimension of the square matrix.
• The next \( n \) lines each contain \( n \) space-separated integers, representing the rows of the matrix.
• The last line contains an integer \( target \) which is the element to search for.

outputFormat

If the target element is found, print two space-separated integers representing its row and column indices (0-indexed) to standard output (stdout). If the target is not present, print -1.

## sample

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