Next Coordinate With Value

M is a non-empty matrix (a list of lists). curr_coords is a (row, column) tuple inside M, and prev_coords is either another such tuple or None.

Write next_coordinate_with_value(curr_coords, value, M, prev_coords) that looks at the four neighbours of curr_coords in the order left, right, up, down and returns the first neighbour that

• lies inside M,
• holds value, and
• is not equal to prev_coords.

If no neighbour qualifies, the function returns None.

Example

With M = [[0, 0, 1], [0, 0, 1], [1, 1, 1]], next_coordinate_with_value((2, 1), 1, M, None) returns (2, 0), while next_coordinate_with_value((2, 1), 1, M, (2, 0)) returns (2, 2).

Your task

Implement this function:

def next_coordinate_with_value(curr_coords, value, M, prev_coords=None):

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: curr_coords, value, M, prev_coords.

Example

Input

(2, 1)
1
[[0, 0, 1], [0, 0, 1], [1, 1, 1]]
None

Output

(2, 0)