{"problem":{"name":"C. Minimal string","description":{"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: *   E","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF797C"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nFirst line contains non-empty string _s_ (1 ≤ |_s_| ≤ 105), consisting of lowercase English letters.\n\n## Output\n\nPrint resulting string _u_.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","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$。\n\n## Input\n\n第一行包含一个非空字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。\n\n## Output\n\n请输出最终得到的字符串 $u$。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF797C","tags":["data structures","greedy","strings"],"sample_group":[["cab","abc"],["acdb","abdc"]],"created_at":"2026-03-03 11:00:39"}}