# Shortest Manhattan Distance

Given an $N \times M$
grid, a person at location $(x,
y)$ can take a step to the left (decreasing $x$ by 1), right (increasing
$x$ by 1), down
(decreasing $y$ by 1), or
up (increasing $y$ by 1).
A *path* from $(x_0, y_0)$ to $(x_1, y_1)$ is a list of steps
(`"left"`, `"right"`, `"up"`, or
`"down"`) that starts at $(x_0, y_0)$ and ends at $(x_1, y_1)$. The length of a path is
the number of steps in the path. The length of a shortest path
between two points is just the Manhattan distance between those
two points:

Your task will be to find *all* the shortest paths
from $(x_0, y_0)$ to
$(x_1, y_1)$.

## Input

The input is composed of a single line with four integers, each separated by a single space: $x_0\; y_0\; x_1\; y_1$ (such that $-3 \le x_0, y_0, x_1, y_1 \le 3$)

## Output

The output will be the shortest paths between $(x_0, y_0)$ and $(x_1, y_1)$, specified as a list of
steps (`"left"`, `"right"`, `"up"`, or
`"down"`), each separated by a single
space.

If there is more than one shortest path, then each line will contain a distinct path. The paths can be printed in any order (i.e., for the given sample input, your output doesnâ€™t have to match our output byte-by-byte, but the individual paths must be correct).

If $(x_0, y_0) = (x_1,
y_1)$, then print `NONE`.

Sample Input 1 | Sample Output 1 |
---|---|

0 0 1 1 |
right up up right |

Sample Input 2 | Sample Output 2 |
---|---|

5 7 5 7 |
NONE |

Sample Input 3 | Sample Output 3 |
---|---|

-1 -1 1 1 |
right right up up right up right up right up up right up right right up up right up right up up right right |