Petya recieved a gift of a string s with length up to 10⁵ 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⁵), consisting of lowercase English letters.

Output

Print resulting string u.

Example

Input

cab

Output

abc

Input

acdb

Output

abdc

有三个串，s，t，u，首先给你s串，然后可以有两种操作，一种是把s串的第一个放在t串的最后，另一种操作时候把t串的最后一个放在u串后面，请输出最后能得到的字典序最小的u串（s串和t串最后都是空的）

解题思路：

逆序维护一个数组c[i]=x，表示第i个位子后边最小的字符是x.

有一个栈充当t串，然后就比对看栈顶元素和c的元素，如果栈顶元素小就直接输出，否则就将s的元素存入栈中

#include<stack>#include<stdio.h>#include<string.h>using namespace std;int main() {    stack <char > a;    char b[110000], c[110000];    int l, i, num;    while(gets(b) != NULL) {        memset(c, 0, sizeof(c));        l = strlen(b);        c[l]=‘z‘;                for(i = l - 1; i >= 0; i--) {            c[i] = min(c[i + 1], b[i]);        }        num = 0;        while(num < l || !a.empty()) {                        if(!a.empty() && a.top() <= c[num]) {                putchar(a.top());                a.pop();            }            else {                a.push(b[num++]);            }        }        printf("\n");    }    return 0;}

Codeforces 797C -Minimal string