Hide

Problem F
Junk Journey

/problems/junkjourney/file/statement/en/img-0001.png
A picture of Sample Input 2. The two leftmost scooters can be pushed in the depot by moving up three times and moving right twice.

You are MALL-E, the mall scooter scooper robot. Your job is to fetch all the misplaced mall scooters at the end of the day and return them to the scooter depot. The mall is an infinite grid, containing $n$ scooters that need to be returned. You can move in one of four directions: up, down, left, or right, and each move takes one second. If you move to a location that contains a scooter, that scooter moves to the next location in the same direction you were moving. If a scooter moves into a location that contains another scooter, the same thing happens, so there is never more than one scooter at each location and you never occupy the same location as a scooter. If a scooter moves to the scooter depot, it disappears. However, the robot can freely move over the scooter depot.

The mall will soon open. You need to find a way to get all the scooters to the depot in at most $10^5$ seconds.

Input

The first line of the input contains a single integer $n$ ($1 \leq n \leq 50$). The next line contains four integers $x_0$, $y_0$, $x_ t$, and $y_ t$ ($0 \leq x_0, y_0, x_ t, y_ t \leq 30$). This indicates that you start at $(x_0, y_0)$ and the depot is located at $(x_ t, y_ t)$. Then follow $n$ lines, each containing two integers $x$ and $y$ ($0 \leq x, y \leq 30$). This indicates that there is a scooter located at $(x, y)$. You, the depot, and all the scooters will all have distinct locations.

Output

The output should contain a sequence of instructions, each on its own line. An instruction is one of the following strings: “up”. “down”, “left”, or “right”.

Sample Input 1 Sample Output 1
1
0 0 2 0
1 0
right
Sample Input 2 Sample Output 2
8
1 1 4 4
5 4
6 4
3 4
2 4
4 5
4 6
4 3
4 2
up
up
up
right
right
down
down
down
right
up
up
right
right
right
up
left
left
up
up
up
left
down
down

Please log in to submit a solution to this problem

Log in