A badly placed word P78721


Statement
 

pdf   zip

thehtml

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