Mars Rover

Ένα πλανητικό "rover" ταξιδεύει σε μια τέλεια επίπεδη επιφάνεια (χωρίς εμπόδια) στον Άρη. Το rover βρίσκεται σε ραδιοεπικοινωνία με το "προσεδάφιο" (lander) στο οποίο έφτασε. Το προσεδάφιο συσσωρεύει και αναμεταδίδει εντολές, τις οποίες λαμβάνει από τη Γη, στο rover. Το rover κάνει πολλές διαδρομές. Κάθε διαδρομή ξεκινά με το rover στο προσεδάφιο, στραμμένο προς μια γνωστή κατεύθυνση. Στο τέλος κάθε εκδρομής, ο προσεδαφιστής πρέπει να υπολογίζει και να μεταδίδει μια σειρά εντολών για να επιστρέψει το rover στο προσεδάφιο.

Το rover ανταποκρίνεται σε μια σειρά εντολών που αποστέλλονται από το προσεδάφιο. Κάθε εντολή λέει στο rover να κινηθεί μπροστά κατά κάποιο πολλαπλάσιο μιας ακριβούς μονάδας απόστασης ή να στρίψει αριστερά ή δεξιά ακριβώς ~90~ μοίρες.

Η εντολή "move ahead" ("προχώρα μπροστά") κωδικοποιείται χρησιμοποιώντας δύο διαδοχικές γραμμές στο αρχείο εισόδου. Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~1~ και η δεύτερη γραμμή περιέχει έναν μη αρνητικό ακέραιο αριθμό ~n~, την απόσταση που πρέπει να προχωρήσουμε προς τα εμπρός. Η εντολή "turn right" ("στροφή δεξιά") κωδικοποιείται χρησιμοποιώντας μια γραμμή εισόδου που περιέχει τον ακέραιο αριθμό ~2~. Η εντολή "turn left" ("στροφή αριστερά") κωδικοποιείται χρησιμοποιώντας μια γραμμή εισόδου που περιέχει τον ακέραιο αριθμό ~3~. Για παράδειγμα, η ακόλουθη σειρά εντολών δίνει εντολή στο rover να στρίψει αριστερά, μετά να προχωρήσει ~10~ μονάδες, μετά να στρίψει δεξιά και μετά να προχωρήσει ~5~ μονάδες.

3
1
10
2
1
5

Το καθήκον σας είναι, δεδομένης μιας τέτοιας σειράς εντολών, να προσδιορίσετε πόσο μακριά πρέπει να ταξιδέψει το rover για να επιστρέψει στο προσεδάφιo και να καθορίσετε τη συντομότερη σειρά εντολών που θα επιστρέψει το rover στο προσεδάφιo. Στο παραπάνω παράδειγμα, το rover πρέπει να ταξιδέψει ~15~ μονάδες για να επιστρέψει και η συντομότερη ακολουθία εντολών είναι:

2
1
10
2
1
5

Το αρχείο εισόδου ξεκινά με μια γραμμή που περιέχει έναν θετικό ακέραιο, ~n~, τον αριθμό των διαδρομών για το rover. Οι εντολές για τις διαδρομές καταλαμβάνουν τις επόμενες γραμμές του αρχείου εισόδου. Κάθε εκδρομή αποτελείται από έναν αριθμό εντολών που ακολουθούνται από μια γραμμή που περιέχει ~0~. Δεν υπάρχουν σφάλματα ή κενές γραμμές στην είσοδο. Το rover διανύει λιγότερες από ~10\,000~ μονάδες απόστασης σε κάθε διαδρομή.

Για κάθε διαδρομή, το αρχείο εξόδου πρέπει να περιέχει μια γραμμή:

Distance is k

όπου ~k~ είναι η απόσταση σε μονάδες που πρέπει να διανύσει το rover για να επιστρέψει στο προσεδάφιο. Οι ακόλουθες γραμμές θα πρέπει να περιέχουν τη συντομότερη σειρά εντολών για την επιστροφή του rover στο προσεδάφιο. Μια κενή γραμμή θα πρέπει να χωρίζει τις γραμμές εξόδου για διαφορετικές διαδρομές.

Σημείωση: Θα δοθούν επιμέρους σημάδια για τις αποστάσεις, χωρίς τα ταξίδια με επιστροφή.

Παράδειγμα

input

3
2
3
3
0
3
1
10
2
1
5
0
1
5
2
1
5
3
3
1
1
0

output

Distance is 0

Distance is 15
2
1
10
2
1
5

Distance is 9
1
4
3
1
5