Word Ladder Transformation

You are given two words: a start word and a target word, and a list of words. Your task is to find the shortest transformation sequence from the start word to the target word, such that:

• Only one letter can be changed at a time.
• Each intermediate word must exist in the given word list.

If there is no valid transformation, output an empty sequence ([]).

Note: The transformation sequence does not necessarily have to be unique. However, the algorithm should return the first valid shortest sequence it finds using a breadth-first search strategy. All formulas and conditions are provided in \(\LaTeX\) format when needed.

For example, for the transformation from hit to cog using the word list [hot, dot, dog, lot, log, cog], a valid answer is hit hot dot dog cog.

inputFormat

The input is read from standard input and has the following format:

1. The first line contains two space-separated strings, the start word and the target word.
2. The second line contains an integer n representing the number of words in the word list.
3. The next n lines each contain a single word from the word list.

All words have the same length.

outputFormat

If a transformation sequence is found, output the sequence as space-separated words in one line.

If no valid transformation exists, output [] (without quotes).

## sample

hit cog
6
hot
dot
dog
lot
log
cog

hit hot dot dog cog