Lexicographical Buffer - Rippling Online Assessment IIT BHU

Problem Preview

"You are given a string `s` consisting strictly of lowercase English letters. You are operating a machine equipped with a stack-like buffer, represented by a string `t` (initially empty). You also have an output display that will show a final string `p` (initially empty). In a single move, you may execute exactly one of the following operations: 1. **Push:** Remove the first character from the string `s` and append it to the end of the buffer `t`. (You can only do this if `s` is not empty). 2. **Pop:** Remove the last character from the buffer `t` and append it to the end of the output string `p`. (You can only do this if `t` is not empty). You must perform these moves until both `s` and `t` are completely empty. Your task is to determine the lexicographically smallest string `p` that can be produced on the output display. ### Input The first and only line of input contains a single string `s` (1 <= |s| <= 100,000) consisting of lowercase English letters. ### Output Print a single string — the lexicographically smallest possible string `p` that can be generated. --- ### Examples **Input** ```text zza ``` **Output** ```text azz ``` **Input** ```text bac ``` **Output** ```text abc ``` **Input** ```text bdda ``` **Output** ```text addb ``` ---"