Valid Adjacent Coordinates

M is a non-empty matrix (a list of lists) in which every row has the same length.

Write valid_adjacent_coordinates(x, y, M) that returns the set of coordinates directly above, below, left of and right of (x, y) that actually lie inside M. Diagonal neighbours do not count. Coordinates that fall outside the matrix are left out, so a 1x1 matrix gives the empty set.

Example

valid_adjacent_coordinates(0, 0, [[0, 0], [0, 0]]) returns {(1, 0), (0, 1)}.

Your task

Implement this function:

def valid_adjacent_coordinates(x: int, y: int, M) -> set:

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: x, y, M.

Example

Input

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

Output

{(0, 1), (1, 0), (1, 2), (2, 1)}