Under construction

Still being built. Things may change

Minsik Language Word Sorting

Interview

Time limit2sMemory limit128 MB

Summary
Sort Minsik language words using a custom 20-letter alphabet where the digraph 'ng' counts as a single letter between 'n' and 'o'.
Level

Medium4 of 10

Topics
String, Sorting, Implementation
Solved
No attempts yet

Problem

The Minsik language has the following 20 letters, and dictionary order follows this order.

a b k d e g h i l m n ng o p r s t u w y

The sequence ng is not two separate letters; it is treated as one letter placed between n and o. Whenever ng appears in a word, compare it as that single letter.

Given several words in the Minsik language, sort them in dictionary order according to this alphabet.

Input

The first line contains the number of Minsik language words, N. N is a positive integer not greater than 50.

Each of the next N lines contains one Minsik language word. Each word has length at most 50. No input word contains a letter outside the Minsik alphabet, and all words are distinct.

Output

Print the sorted words, one per line.

Examples6

  1. Example 1

    Input
    4
abakada
alpabet
tagalog
ako
    Expected output
    abakada
ako
alpabet
tagalog

  2. Example 2

    Input
    6
ang
ano
anim
alak
alam
alab
    Expected output
    alab
alak
alam
anim
ano
ang

  3. Example 3

    Input
    6
siya
niya
kaniya
ikaw
ito
iyon
    Expected output
    kaniya
ikaw
ito
iyon
niya
siya

  4. Example 4

    Input
    5
kaba
baka
naba
ngipin
nipin
    Expected output
    baka
kaba
naba
nipin
ngipin

  5. Example 5

    Input
    7
knilngiggnngginggn
ingkigningg
kingkong
dingdong
dindong
dingdont
ingkblot
    Expected output
    kingkong
knilngiggnngginggn
dindong
dingdont
dingdong
ingkblot
ingkigningg

  6. Example 6

    Input
    4
silangang
baka
bada
silang
    Expected output
    baka
bada
silang
silangang