Password Combination

In the field of information security, passwords play an invaluable role. A brute‐force attack on a login password means trying every possible letter combination, which is time‐consuming and prone to detection. In order to reduce the number of attempts, attackers first gather "observations" in the following format:

I observed that the password contains the substring ***.

For example, if the target password is of length \(10\) and the two observed substrings are hello and world, one may form the passwords \[ \texttt{helloworld} \quad \text{and} \quad \texttt{worldhello} \] If the target password is of length \(6\) and the observed strings are good and day, then one possible combination is \[ \texttt{gooday} \] Here, note that the two substrings may overlap. In the first example there is no overlap (overlap length \(x=0\)), but in the second example the strings overlap by one character (since \(4+3-6=1\)) and the last letter of good matches the first letter of day.

Your task is to write a program that, given the length of the password and the two observed substrings (which only contain lowercase letters \(a\text{--}z\)), computes all possible password combinations. There are only two possible orders: first s₁ then s₂, or first s₂ then s₁. For an order, if we let \(L_1\) and \(L_2\) be the lengths of the two substrings respectively, then the required overlap length is given by the formula \[ x = L_1 + L_2 - n \] It is valid only if \(0 \le x \le \min(L_1, L_2)\) and the overlapping parts match exactly. If no valid combination exists, output 0.

inputFormat

The input consists of a single line containing three tokens separated by spaces. The first token is an integer \(n\) representing the length of the password, and the next two tokens are the observed substrings.

For instance:

10 hello world

outputFormat

If one or more valid password combinations exist, print each unique combination on a new line in lexicographical order. If no valid combination exists, output 0.

sample

10 hello world

helloworld
worldhello