Capitalization of Phrases with Exceptions

Your task is to transform a given input string by capitalizing the first letter of each word according to specific rules. More formally, given a string \( s \) consisting of several words separated by spaces, you need to transform it such that:

• The first and last words are always capitalized (i.e. their first letter in uppercase).
• Any word that is not the first or last one is capitalized if and only if it does not belong to the set of exception words \( E = \{\text{and}, \text{the}, \text{in}, \text{of}, \text{on}, \text{with}\} \); otherwise, it remains unchanged.

For example, given the input string "the quick brown fox jumps over the lazy dog", the correct output is "The Quick Brown Fox Jumps Over the Lazy Dog". Notice that although "the" is an exception, it appears as the first word, so it is capitalized; similarly, if an exception word appears at the end, it should be capitalized.

Input is provided via standard input (stdin) and the resulting string should be printed to standard output (stdout).

inputFormat

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

Input is read from stdin.

outputFormat

Output the transformed string that meets the capitalization rules described above.

Output to stdout.

the quick brown fox jumps over the lazy dog

The Quick Brown Fox Jumps Over the Lazy Dog