Search in a Sorted Matrix

You are given a matrix where each row and each column is sorted in ascending order. Your task is to find the position of a target integer in the matrix using an efficient search algorithm. Specifically, you should implement the following:

Given a matrix \( A \) of dimensions \( r \times c \) where each row and each column is sorted in increasing order, and a target integer \( t \), find indices \( (i, j) \) such that \( A[i][j] = t \). If the target is not found, output None.

Constraints: \( 1 \le r, c \le 10^3 \). You may assume all numbers are integers. Use an algorithm with time complexity \( O(r + c) \).

Example:

Input:
4 4
1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17
5
Output:
1 1

</p>

inputFormat

The input is given from standard input (stdin) and is formatted as follows:

• The first line contains two space-separated integers: r (number of rows) and c (number of columns).
• The next r lines each contain c space-separated integers representing the matrix.
• The final line contains the target integer t.

outputFormat

Output to standard output (stdout) a single line containing the row and column indices (0-indexed) separated by a space if the target is found. If the target is not present in the matrix, print None (without quotes).

## sample

4 4
1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17
5

1 1

</p>