Suggested Products

You are given distinct product names and a search word. After each character of the search word is typed, output at most 3 lexicographically smallest products among all products matching the current prefix.

This site added the standard input/output protocol.

输入格式

The first line contains n m (1 ≤ n,m ≤ 1000); the second line contains n product names without whitespace; the third line contains the search word. Product names and the search word contain only lowercase English letters.

输出格式

Output one line for each non-empty prefix of the search word. The line lists at most 3 smallest matching products in lexicographic order; output - if nothing matches.

样例 1

输入：

4 4
abcd abba adbc abcc
abcd

输出：

abba abcc abcd
abba abcc abcd
abcc abcd
abcd

样例 2

输入：

3 1
b a ba
c

输出：

-

样例 3

输入：

4 2
ba bb bc bd
ba

输出：

ba bb bc
ba