#243EasyMatrix· Row Minima and Column Maxima

Saddle Seat Finder

A concert hall rates every seat with a comfort score. The seats form a grid: each row is a row of the hall and each column is an aisle of seats. A seat is called a **saddle seat** if its score is - less than or equal to every score in its row, and - greater than or equal to every score in its column. Return the scores of all saddle seats, listed row by row (top to bottom, left to right within a row). Equal scores of different seats are all reported.

Input format

`grid`: a non-empty rectangular matrix of integers, `grid[r][c]` being the score of the seat in row `r`, column `c`.

Output format

An array of the saddle seat scores in row-major order, empty if there is none.

Examples

Input: grid = [[3, 7, 8], [9, 11, 13], [15, 16, 17]]

Output: [15]

The row minima are 3, 9 and 15; the column maxima are 15, 16 and 17. Only the seat with score 15 is a minimum of its row and a maximum of its column.

Input: grid = [[7, 7], [7, 7]]

Output: [7, 7, 7, 7]

Every seat equals every other, so all four satisfy both conditions and all four scores are reported.

Input: grid = [[1, 2], [2, 1]]

Output: []

No seat is both a row minimum and a column maximum, so the result is empty.

Constraints

1 <= rows, cols <= 300
-10^5 <= grid[r][c] <= 10^5

#matrix
#arrays
#traversal
#precomputation