#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <string>#include <queue>#include <stack>#include <vector>#include <algorithm>using namespace std;char s[100010];char m[100010];stack<char>st;int main(){	scanf("%s",s);		int len = strlen(s);	m[len-1] = s[len-1];	for(int i=len-2;i>=0;i--)	{		m[i] = min(m[i+1],s[i]);	}	for(int i=0;i<len;i++)	{		if(s[i] == m[i]) 		{			while((!st.empty())&&(st.top()<=s[i]))			{				printf("%c",st.top());				st.pop();			}			printf("%c",s[i]);		}		else 		{			while((!st.empty())&&(st.top()<=m[i]))			{				printf("%c",st.top());				st.pop();			}			st.push(s[i]);		}	}	while(!st.empty())	{		printf("%c",st.top());		st.pop();	}	printf("\n");	return 0;}