Shortest Contiguous Subsequence with Target Subsequence

You are given a list of words and a target string. Your task is to find the shortest contiguous subsequence of the words such that when the words are concatenated in order, the resulting string contains the target string as a subsequence.

A string S is said to be a subsequence of another string T if there exist indices \(i_1 < i_2 < \cdots < i_m\) in \(T\) such that \(T[i_1]T[i_2]\cdots T[i_m] = S\). In other words, all characters of S must appear in T in the same order, but not necessarily consecutively.

If there is no such contiguous subsequence that satisfies the condition, output an empty line.

inputFormat

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

n
w1 w2 ... wn
target

Where:

• n is an integer representing the number of words.
• w1, w2, ..., wn are the words separated by spaces.
• target is the target string you need to check as a subsequence.

outputFormat

Print to stdout the words in the shortest contiguous subsequence separated by a single space. If no valid subsequence exists, print an empty line.

5
abc de fg hij kl
fgh

fg hij