Locate a Value in a Row-Sorted Matrix

matrix has m rows and n columns. Each row is sorted in increasing order, and the first value of every row is larger than the last value of the previous row. Return [row, col] of target if it is present, otherwise [-1, -1]. All values are distinct.

Examples

Input:  matrix = [[1, 3, 5], [7, 9, 11], [13, 15, 17]], target = 9
Output: [1, 1]

Input:  matrix = [[1, 3, 5], [7, 9, 11], [13, 15, 17]], target = 4
Output: [-1, -1]

Constraints

• 1 <= m, n <= 1000
• -10**9 <= matrix[i][j], target <= 10**9
• O(log(m * n)) time; scanning rows is too slow.

Goals

• Treat a 2D grid as one flat sorted sequence
• Convert a flat index back to (row, column)