You are given a string originalString consisting of lowercase English letters.

Initially, two empty strings are available:

temporaryString encodedString

You may perform the following operations any number of times until originalString and temporaryString are both empty.

Operation 1

Remove the first character of originalString and append it to the end of temporaryString.

Operation 2

Remove the last character of temporaryString and append it to the end of encodedString.

At any step, you may perform either operation whenever it is valid.

Your task is to determine the lexicographically smallest possible encodedString that can be obtained after processing all characters.

Notes temporaryString behaves like a stack. Every character from originalString must appear exactly once in encodedString. A valid sequence of operations must eventually empty both originalString and temporaryString. Function Signature string smallestEncodedString(string originalString); Input

A single string originalString.

Output

Return the lexicographically smallest possible encodedString.

Constraints 1 ≤ |originalString| ≤ 2 × 10^5 originalString contains only lowercase English letters ('a'–'z'). Example 1

Input

bac

Output

abc

Explanation

One optimal sequence of operations is:

original: bac temp: "" encoded: ""

Move 'b' to temp. temp = "b"

Move 'a' to temp. temp = "ba"

Move 'a' from temp to encoded. encoded = "a"

Move 'b' from temp to encoded. encoded = "ab"

Move 'c' to temp. temp = "c"

Move 'c' from temp to encoded. encoded = "abc"

No other valid sequence produces a lexicographically smaller string.

Example 2

Input

zza

Output

azz"

Explanation

By delaying the removal of the two 'z' characters until after 'a' has been moved to temporaryString, the smallest possible encoded string is "azz".