410472: GYM104024 D Bookworm

As a total bookworm, doing a lot of reading every day is an integral part of Waff's life. After reading all the books several times over, Waff found the old way of reading too boring.

Now, Waff plans to pick a book from his shelf first, and when he finishes it, the title of the next book must be the result of adding an arbitrary letter in any one place(at the beginning, between two letters, or at the end) to the title of this book. Waff then repeats this process until there are no more books to read that satisfy the condition. For example, if the book Waff is reading is called tom, the title of the next book that satisfies the condition can be atom, toom, or tomb, but can't be to and ttomm.

Waff has $$$N$$$ books on his bookshelf, and the titles of all the books are strings of lowercase letters only. Now that Waff has selected the book he wants to read, then he wants to know what the longest title he can read is.

The input is guaranteed to have a unique solution.

Line 1: An integer $$$N\ (1 \le N \le 1000)$$$ followed by a legal word, representing the first book he will read.

Line 2 to $$$N+1$$$: Each line contains a legal word less than $$$80$$$ letters long, consisting only of lowercase letters.

A single line contains a word, representing the longest title Waff can read.

7 tom
to
tom
atom
atoma
tomb
tomba
tombau

tombau

The reading sequence in testcase: tom, tomb, tomba, tombau.