You are given a string s consisting strictly of lowercase English letters. You are operating a machine equipped with a stack-like buffer, represented by a string t (initially empty). You also have an output display that will show a final string p (initially empty).

In a single move, you may execute exactly one of the following operations:

1. Push: Remove the first character from the string s and append it to the end of the buffer t. (You can only do this if s is not empty).
2. Pop: Remove the last character from the buffer t and append it to the end of the output string p. (You can only do this if t is not empty).

You must perform these moves until both s and t are completely empty.

Your task is to determine the lexicographically smallest string p that can be produced on the output display.

Input

The first and only line of input contains a single string s (1 <= |s| <= 100,000) consisting of lowercase English letters.

Output

Print a single string — the lexicographically smallest possible string p that can be generated.

---

Examples

Input

zza

Output

azz

Input

bac

Output

abc

Input

bdda

Output

addb

---