Dynamic median P37064


Statement
 

pdf   zip

thehtml

Given a sequence of words, print the median of all the words seen so far at every moment. Please recall that the median of a set of n elements is the element that would be in the position ⌊ (n + 1)/ 2 ⌋ if the set was ordered. For example, the median of five elements is the third smallest, and the median of six elements is also the third smallest.

Input

Input consists of a sequence of different lowercase words ended in “END”.

Output

For every word in the input, print the median of the words read so far. Suppose that the words are sorted with the usual alphabetical order.

Public test cases

  • Input

    hola
bye
adeu
hi
hello
END

    Output

    hola
bye
bye
bye
hello

  • Input

    a
b
c
d
e
f
END

    Output

    a
a
b
b
c
c

  • Input

    f
e
d
c
b
a
END

    Output

    f
e
e
d
d
c
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C C++ Python