Reverse Lexicographical Order

Given a string containing words separated by single spaces, your task is to rearrange the words in reverse lexicographical order.

For example, given the input string "the quick brown fox jumps over the lazy dog", the words sorted in reverse lexicographical order are "the the quick over lazy jumps fox dog brown".

Note: Sorting is based on the standard lexicographical (dictionary) order but in reverse. If the input string is empty, output an empty string.

The ordering can be mathematically described as follows. Let \( S = \{w_1, w_2, \dots, w_n\} \) be the set of words in the input string, then the output is a permutation \( S' \) such that for every \( i < j \), we have \( w'_i \geq w'_j \) in lexicographical order.

inputFormat

The input consists of a single line containing a string \( S \) with words separated by single spaces. The string may be empty.

outputFormat

Output a single line containing the words of \( S \) rearranged in reverse lexicographical order, separated by single spaces.

the quick brown fox jumps over the lazy dog

the the quick over lazy jumps fox dog brown