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++ Python