Mirror The Path Horizontally

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 mirror_horizontally(M) that finds the path and then also marks the horizontal mirror image of every path cell with a 1: the cell at row i, column j is mirrored to row i, column (number of columns - 1) - j. The original path cells stay as they are. Modify M in place and return it.

Example

For M = [[1, 0, 0], [1, 0, 0], [1, 1, 1]] the result is [[1, 0, 1], [1, 0, 1], [1, 1, 1]].

Your task

Implement this function:

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

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