Word Ladder Transformation

You are given two words: a beginWord and an endWord, and a list of words called wordList. Your task is to find the shortest transformation sequence from beginWord to endWord such that:

• Only one letter can be changed at a time.
• Each transformed word (except for beginWord) must exist in wordList.

In other words, if we denote two words as a and b each of length \(n\), then a can be transformed to b if and only if: \[ \sum_{i=1}^{n} \mathbf{1}\{a_i \neq b_i\} = 1. \]

If there is no valid transformation sequence, output []. If beginWord is the same as endWord, then the answer is simply beginWord.

inputFormat

The input is given via stdin in the following format:

<beginWord> <endWord>
<n>
<word1> <word2> ... <word_n>

Where:

• The first line contains two strings separated by a space: beginWord and endWord.
• The second line contains an integer n that denotes the number of words in the word list.
• The third line contains n words separated by spaces.

outputFormat

The output should be printed to stdout as a single line:

• If a valid transformation sequence exists, output the sequence of words separated by a single space.
• If no sequence exists, output [] (including the square brackets).

## sample

hit cog
6
hot dot dog lot log cog

hit hot dot dog cog