Alternate 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 alternate_path(M) that finds the path and then rewrites its cells with alternating values: the start cell becomes 1, the next cell 2, the next 1, and so on. Cells that are not on the path keep their value. Modify M in place and return it.

Example

For M = [[1, 0, 0], [1, 0, 0], [1, 1, 1]] the path is [(2, 2), (2, 1), (2, 0), (1, 0), (0, 0)], so the result is [[1, 0, 0], [2, 0, 0], [1, 2, 1]].

Your task

Implement this function:

def alternate_path(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

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