Description

Given $N$ words and a string $T$, output all words that have $T$ as a prefix, in lexicographical order.

Input Format

The first line contains a positive integer $N$. The next $N$ lines each contain one word, with length at most $100$. The last line contains the string $T$.

Output Format

Output all such words in ascending lexicographical order.

6
na
no
ki
ki
ka
ku
k

ka
ki
ki
ku

Hint

Constraints

• For $60\%$ of the testdata, $1 \le N \le 1000$.
• For $100\%$ of the testdata, $1 \le N \le 100000$ and all characters are lowercase letters.

Translated by ChatGPT 5