Follow The Path

A path matrix is a matrix of 0s and 1s that holds a single continuous path of 1s. The path starts at the rightmost 1 of the last row and ends at the leftmost 1 of the first row. It does not branch, and it moves only horizontally and vertically.

matrix = [
    [0, 0, 1, 1],
    [0, 0, 0, 1],
    [1, 1, 1, 1],
    [1, 0, 0, 0],
    [1, 1, 0, 0]
]

Write get_path_coordinates(M) that walks along the path and returns the list of its coordinates as (row, column) tuples, from the start cell to the end cell.

For the matrix above the result is [(4, 1), (4, 0), (3, 0), (2, 0), (2, 1), (2, 2), (2, 3), (1, 3), (0, 3), (0, 2)].

If the start cell is also the end cell, the result is a list with that single coordinate.

Your task

Implement this function:

def get_path_coordinates(M):

Write the function only — the arguments are read for you and the return value is printed automatically.

Arguments arrive as one Python literal per line, in this order: M.

Example

Input

[[0, 0, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1], [1, 0, 0, 0], [1, 1, 0, 0]]

Output

[(4, 1), (4, 0), (3, 0), (2, 0), (2, 1), (2, 2), (2, 3), (1, 3), (0, 3), (0, 2)]