{"raw_statement":[{"iden":"statement","content":"Petya recieved a gift of a string _s_ with length up to 105 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:\n\n*   Extract the **first** character of _s_ and append _t_ with this character.\n*   Extract the **last** character of _t_ and append _u_ with this character.\n\nPetya wants to get strings _s_ and _t_ empty and string _u_ lexicographically minimal.\n\nYou should write a program that will help Petya win the game."},{"iden":"input","content":"First line contains non-empty string _s_ (1 ≤ |_s_| ≤ 105), consisting of lowercase English letters."},{"iden":"output","content":"Print resulting string _u_."},{"iden":"examples","content":"Input\n\ncab\n\nOutput\n\nabc\n\nInput\n\nacdb\n\nOutput\n\nabdc"}],"translated_statement":[{"iden":"statement","content":"Petya 收到了一个长度最多为 $10^5$ 个字符的字符串 $s$ 作为生日礼物。他取了两个空字符串 $t$ 和 $u$，并决定玩一个游戏。这个游戏有两种可能的操作：\n\nPetya 希望最终让字符串 $s$ 和 $t$ 都变为空，而字符串 $u$ 字典序最小。\n\n你需要编写一个程序帮助 Petya 赢得这个游戏。\n\n第一行包含一个非空字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。\n\n请输出最终得到的字符串 $u$。"},{"iden":"input","content":"第一行包含一个非空字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。"},{"iden":"output","content":"请输出最终得到的字符串 $u$。"},{"iden":"examples","content":"输入\ncab\n输出\nabc\n\n输入\nacdb\n输出\nabdc"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\Sigma^* $ be the input string, where $ \\Sigma = \\{a, b, \\dots, z\\} $ and $ 1 \\leq |s| \\leq 10^5 $.  \nLet $ t = \\varepsilon $, $ u = \\varepsilon $ be initial empty strings.  \n\n**Operations**  \nAt each step, one of the following moves is performed:  \n1. Move the first character of $ s $ to the end of $ t $.  \n2. Move the last character of $ t $ to the end of $ u $.  \n\n**Objective**  \nTransform $ s $ and $ t $ to empty strings, and maximize the lexicographical minimality of $ u $.  \n\n**Output**  \nThe lexicographically minimal string $ u \\in \\Sigma^* $ achievable through any sequence of valid moves.","simple_statement":null,"has_page_source":false}