Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Minimal string

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPetya recieved a gift of a string *s* with length up to 10^{5} characters for his birthday. He took two more empty strings *t* and *u* and decided to play a game. This game has two possible moves:

- Extract the first character of
*s*and append*t*with this character. - Extract the last character of
*t*and append*u*with this character.

Petya wants to get strings *s* and *t* empty and string *u* lexicographically minimal.

You should write a program that will help Petya win the game.

Input

First line contains non-empty string *s* (1 ≤ |*s*| ≤ 10^{5}), consisting of lowercase English letters.

Output

Print resulting string *u*.

Examples

Input

cab

Output

abc

Input

acdb

Output

abdc

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2018 04:16:06 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|