Under construction

Still being built. Things may change

Gahui and the File Explorer

Time limit1.5sMemory limit512 MB

Summary
Sort N filenames by name, then by whether the extension is OS-recognized, then by extension, all in ASCII order.
Level

Medium4 of 10

Topics
Sorting, String, Hash map, Implementation
Solved
No attempts yet

Problem

Gahui is inside the jo_test folder. She wants to sort the N files in jo_test by the following criteria.

  1. By filename (FILENAME) in lexicographic order
  2. If the filenames (FILENAME) are equal, files whose extension is recognized by the OS Gahui has installed come first
  3. If criteria 1 and 2 still do not decide the order, by file extension (EXTENSION) in lexicographic order

Sort the N files by the sorting criteria described in the problem. Lexicographic order follows ASCII code order.

Input

The first line gives the number of files N in the jo_test folder and the number of file extensions M recognized by the OS Gahui has installed, separated by a space.

Lines 2 through N+1 each give a string of the form FILENAME.EXTENSION. Here the . means a period.

FILENAME consists of lowercase letters and digits only, and EXTENSION consists of lowercase letters only.

Starting on the next line, the M file extensions (EXTENSION) recognized by the OS Gahui has installed are given.

Output

Print the result sorted by the criteria.

Constraints

  • 1 ≤ N ≤ 2×10^5
  • 1 ≤ M ≤ 2×10^5
  • The lengths of a file extension and a filename do not exceed 10.
  • The N given FILENAME.EXTENSION strings are distinct.
  • The M file extensions recognized by the OS Gahui has installed are distinct.

Examples2

  1. Example 1

    Input
    5 3
abc.jpeg
abc.jpg
foo.yolo
bar.cpp
bar.maltise
jpg
cpp
maltise
    Expected output
    abc.jpg
abc.jpeg
bar.cpp
bar.maltise
foo.yolo

  2. Example 2

    Input
    5 1
vvv.busan
dongdaegu.miryang
gupo.busan
train1225.mugunghwa
trainer.jpg
jpg
    Expected output
    dongdaegu.miryang
gupo.busan
train1225.mugunghwa
trainer.jpg
vvv.busan