Curiosity is the rover that explores the Gale Crater on Mars. Recently it found an evidence of water in Martian soil, which will make it easier to plan the future manned missions.
Curiosity can communicate with Earth directly at speeds up to 32 Kbit/s, but on average 14 minutes and 6 seconds will be required for signals to travel between Earth and Mars.
“You have just seen a stone and applied brakes, but you know that the rover is already passing that stone” — Matt Heverly, the rover’s driver, explains. “So we just plan the route, then write down a list of simple textual commands: move one meter ahead, turn left, make a photo and so on”.
Sometimes it is necessary to react very fast to some unexpected events. For example, if the cameras have seen something interesting, then you might want to change the route of the rover to make an additional photo. To do that, you send a substitution command of the form s/〈string〉/〈replacement〉/g. This replaces all occurrences of 〈string〉, starting with the leftmost one, to 〈replacement〉.
More formally, if A is a non-empty string and B is a string, then to apply the substitution command s/A/B/g to a string S, you should do the following:
This means that:
You know that the longer is the command, the bigger is the time necessary to transmit it. So, you have to write a program that finds shortest command that transforms the initial string to the final string.
The first line contains the initial and the final strings. Both strings are non-empty and their lengths do not exceed 2000 characters. The strings contain only English letters, spaces and punctuation signs (commas, colons, semicolons and hyphens: ‘,’, ‘:’, ‘;’, ‘-’). The given strings are not equal.
Output the substitution command that transforms initial string to final string and has the minimum length. If there are several shortest substitution commands, output any of them.
move left, move right; move up move left, move down, move up
If not found: move x; else move -x If found: move x; else move -x