A badly placed word P78721


Statement
 

pdf   zip

Write a program that, given an almost sorted sequence of words with exactly one word that appears too soon, prints the sequence totally sorted.

Input

Input consists of two or more words made up only of lowercase letters. All the words are different. The sequence is alphabetically sorted except for a word that appears too soon. The end of input is marked with the special word “END”.

Output

Print the sequence totally sorted.

Observation

In this problem, you should not use vectors, lists, or alike.

Public test cases

  • Input

    a
b
e
c
d
f
g
END

    Output

    a
b
c
d
e
f
g

  • Input

    hola
bye
END

    Output

    bye
hola

  • Input

    f
aaaaaa
bbbbb
cccc
ddd
ee
END

    Output

    aaaaaa
bbbbb
cccc
ddd
ee
f
    • Information
    Author
    Jordi Cortadella
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python