Problem Description

Curiosity is the rover that explores the Gale Crater on Mars. Recently, it found evidence of water in Martian soil, which will make future manned missions easier.

Curiosity can communicate with Earth directly at speeds up to $32 Kbit/s$, but on average, $14$ minutes and $6$ seconds are 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 quickly to unexpected events. For example, if the cameras see something interesting, you might want to change the rover's route to take additional photos. 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, with $〈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:

1. Find the leftmost occurrence of A in $S$, such that $S =$ SL $+$ A $+$ SR.
2. If there is no such occurrence, stop. Then, $S$ is the answer.
3. Let $R$ be the result of applying $s/A/B/g$ to SR.
4. The answer is SL $+ B + R$.

This means that:

• If there are two overlapping occurrences of A in $S$, only the leftmost one is replaced. For example, applying $`s/aba/c/g`$ to abababa yields cbc: after replacing the first occurrence of aba, the string becomes cbaba, and only the last occurrence of aba can be replaced after that.
• No substitution uses the results of previous substitutions. For example, applying $`s/a/ab/g`$ to a yields ab, applying $`s/a/ba/g`$ to a yields ba.

The longer the command, the longer it takes to transmit. Therefore, you need to write a program that finds the shortest command that transforms the initial string into the final string.

Input Format

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 Format

Output the substitution command that transforms the initial string into the final string and has the minimum length. If there are several shortest substitution commands, output any of them.

Sample Input and Output

Sample Input #1

move left, move right; move up
move left, move down, move up

Sample Output #1

s/right;/down,/g

Sample Input #2

If not found: move x; else move -x
If found: move x; else move -x

Sample Output #2

s/ not//g

Sample Input #3

abababa
cbc

Sample Output #3

s/aba/c/g

Notes/Hints

Time limit: 2 s, Memory limit: 256 MB.

见题面 Input 部分

见题面 Output 部分