Shortest Substitution Command

Curiosity, the Mars rover, receives commands as simple textual instructions. One such command is a substitution command of the form \(s/A/B/g\), which replaces every occurrence of a non‐empty string \(A\) in a given string with string \(B\) (following the leftmost, non‐overlapping rule).

More formally, to apply the substitution command \(s/A/B/g\) to a string \(S\):

1. Find the leftmost occurrence of \(A\) in \(S\), so that \(S = SL + A + SR\). If no occurrence exists, stop and return \(S\).
2. Then let \(R\) be the result of applying \(s/A/B/g\) to \(SR\) (note that the substitution does not act on the replaced part \(B\)).
3. The final answer is \(SL + B + R\).

For example, applying \(s/aba/c/g\) to abababa results in cbc:

abababa  -- replace leftmost "aba" --> cbaba
cbaba    -- now, the leftmost "aba" is replaced --> cbc

Your task is: given an initial string and a final string, find a substitution command \(s/A/B/g\) that transforms the initial string into the final string. Moreover, since longer commands require more transmission time, you must choose one with the minimal total length. The length of a command is defined as \(|A| + |B| + 5\) (with the added 5 characters corresponding to the fixed parts of the command: s///g).

Note:

• If the initial string is already equal to the final string, you may output a command that makes no changes. In such a case, you can choose any non-empty \(A\) which does not occur in the initial string and use an empty replacement \(B\), resulting in no substitution.
• You are guaranteed that a solution exists.

inputFormat

The input consists of two lines:

• The first line contains the initial string \(S\).
• The second line contains the final string \(T\).

Both strings may consist of any visible characters.

outputFormat

Output a single line containing the substitution command in the format s/A/B/g that transforms \(S\) into \(T\) and minimizes \(|A| + |B| + 5\).

sample

abababa
cbc

s/aba/c/g