Pacific Atlantic Water Flow

MediumGraphs
Next
GraphMatrixDFSMulti-source

A grid of heights is bordered by the Pacific Ocean on the top and left edges and the Atlantic Ocean on the bottom and right edges. Water flows from a cell to a neighbouring cell (up, down, left or right) whose height is equal or lower. Find every cell from which water can flow to both oceans.

Input

Line 1: r and c. Next r lines: c heights each.

Output

Print each qualifying cell as 'row column' (0-based) on its own line, in ascending row then column order.

Constraints

1 <= r, c <= 15 0 <= height <= 9

Example 1
Input
2 2
1 1
1 1
Output
0 0
0 1
1 0
1 1

On a flat grid every cell reaches both oceans.

Hints

Pacific Atlantic Water Flow - Medium Graphs Problem | Skill Shiksha