EIU Programming Practices and Exams

Give the root folder, and data describing the folder tree, including the folders and files. Assuming there are no empty directories, write a program to find all the filenames which is no more than k-th level that contain the given strings. The results are exported in alphabetical order (the path) of the file.

Input

The first line contains an integer n, the number of files and directories in the root directory (including the root directory) (n <= 10 ^ 5)

n -1 the next line contains 2 words, bi is the directory containing bi or anyone containing bi folder.

The next line is the name of the root directory.

The next line contains the word s, which is the keyword to search for in the file names.

The last line is an integer k (0 <= k <n)

Output

Export the File name. At each directory, search alphabetically for children and files (regardless of file and folder).

Note: Folder and File names are case-sensitive. When working with C #, the following methods should be used: public int IndexOf (String value, StringComparison comparisonType), and public int CompareOrdinal (String strA, String strB)

Example

Input:
7
documents DataMining
Report.docx DataMining
Web documents
Web Source
Source Libary.sln
Web Angular.pptx
documents
ar
2
Output:
Angular.pptx