A planetary "rover" is travelling on a perfectly level surface (no obstacles) on Mars. The rover is in radio communication with the "lander" it arrived in. The lander accumulates and relays commands, which it receives from Earth, to the rover. The rover makes several excursions. Each excursion begins with the rover at the lander facing in a known direction. At the end of each excursion, the lander must compute and transmit a sequence of instructions to return the rover to the lander.
The rover responds to a sequence of commands sent from the lander. Each command tells the rover to move ahead some multiple of an exact unit of distance, or to turn left or right exactly 90 degrees.
move ahead command is encoded using two consecutive lines in the input file. The first line contains the integer
1, and the second line contains a non-negative integer , the distance to move forward.
turn right command is encoded using a single input line containing the integer
turn left command is encoded using a single input line containing the integer
For example, the following sequence of commands instructs the rover to turn left, then move ahead 10 units, then turn right, and then move ahead 5 units.
3 1 10 2 1 5
Your task is, given such a sequence of commands, to determine how far the rover must travel to return to the lander, and to determine the shortest sequence of commands that will return the rover to the lander. In the example above, the rover must travel 15 units to return, and the shortest sequence of commands is
2 1 10 2 1 5
The input begins with a line containing a positive integer, , the number of excursions for the rover. The commands for excursions occupy subsequent lines of the input file. Each excursion consists of a number of commands followed by a line containing
0. There are no errors or blank lines in the input. The rover travels less than units of distance on each excursion.
For each excursion, the output should contain a line:
Distance is k
where is the distance in units that the rover must travel to return to the lander. The following lines should contain the shortest sequence of commands to return the rover to the lander. A blank line should separate the lines of output for different excursions.
3 2 3 3 0 3 1 10 2 1 5 0 1 5 2 1 5 3 3 1 1 0
Distance is 0 Distance is 15 2 1 10 2 1 5 Distance is 9 1 4 3 1 5