Longest Lexicographical Substring

Given a string s consisting of lowercase English letters, your task is to find the longest substring that satisfies both of the following conditions:

• The characters in the substring are in strictly lexicographical (increasing) order. In other words, for any two consecutive characters c_i and c_i+1 in the substring, it must hold that c_i < c_i+1.
• All characters in the substring are distinct.

If there are multiple possible substrings with maximum length, the one that appears first in the string when scanning from left to right is taken.

Note: A substring is a contiguous sequence of characters within the string.

The lexicographical condition can be summarized in LaTeX as: $$c_i < c_{i+1} \quad \text{for all valid } i.$$

inputFormat

The input consists of a single line containing the string s composed only of lowercase English letters.

You can assume that s is non-empty.

outputFormat

Output the longest substring that has characters in strictly increasing lexicographical order and all distinct characters, based on the conditions described above.

abcabca

abc