Word Frequency Sorter

medium

Given a string containing a series of words separated by spaces, write a function that returns a new string where the words are sorted based on their frequency of occurrence in descending order. In case two words have the same frequency, sort the words alphabetically.

Example 1

Input

[
  "word word repeat repeat repeat"
]

Output

repeat word

Explanation. The word 'repeat' occurs 3 times and the word 'word' occurs 2 times.

Example 2

Input

[
  "this is is a test test test string"
]

Output

test is this a string

Explanation. 'test' appears 3 times, 'is' appears 2 times, and the other words appear once, sorted alphabetically.

Example 3

Input

[
  "single"
]

Output

single

Explanation. The string contains only one word, so it is output as is.

Example 4

Input

[
  "word another word"
]

Output

word another

Explanation. 'word' appears twice and 'another' appears once.

Follow-up: How would your solution change if punctuations, numbers, and uppercase letters were included in the input?

Constraints:

The input string will include only lowercase letters and space characters. It is guaranteed to contain at least one word.