Катя вирішила розмістити на стіні своєї кімнати своє власне родовідне дерево. Родовідне дерево будується просто: \begin{itemize} \item Корінь дерева - це сама Катя. \item У Каті єь мама і тато - це ліве і праве піддерева. \item Мама і тато є у кожної людини, відповідно, у кожного вузла у дереві також повинні бути ліві і праві піддерева. Але, на жаль, не усіх своїх пра-пра-бабусь і пра-пра-дідусів Катя знає. Тому є деякі вузли, у яких немає одного або навіть двох піддерев. \end{itemize} У кожному вузлі Катя повісила портрети своїх родичів, а у корні дерева - свій власний портрет. Получилось просто відмінно! \includegraphics{https://static.e-olymp.com/content/86/86054c60b3a94acf1e19d5d72bb3f08d421d1b4c.jpg} У Кати є молодший брат Антон, який зрозумів, що Катькине родовідне дерево гарно перетворюється у його власне, достатньо лише замінити портрет у кореневому вузлі. Потім він подумав ще трішки, і вирішив, що дерево можна зробити спільним, достатньо у корневому вузлі повісити його з сестрою спільний портрет. Але раз вже дерево спільне, Антон вирішив внести і свою долю праці у його оформленння. Саме просте - усі портрети помістити у власноруч виготовлені Антоном рамочки, тим більше, що у дитячому садку їх нещодавно навчили робити приголомшливо красиві рамочки. І Антон прийнявся за справу... Скоро у нього було цілком достатоньо прекрасних різнокольорових рамочок. Коли Каті не було удома, він вирішив здійснити свій план. Спочатку Антон зняі усі листки, починаючи цю операцію зліва направо. (Для тих, хто ще не знає, лист - це вершина, у якої немає піддерев.) Зняті портрети Антон склав у стопку і переніс до себе у кімнату. Потім повернувся у кімнату Каті і повторив процедуру. В решті решт на стіні залишився лише портрет Каті. Антон переніс и цей портрет до себе. І ось тут Антон з жахом зрозумів, що відновити дерево по стопкам портретов, що у нього залишились, він не зможе! Катя скоро прийде з університету і Антон відчуває, що у нього будуть великі неприємності. Допоможіть Антошці ввідновити дерево! Вам повинні допомогти буквені позначки, якими Катя помітила усі вузли дерев. Кожен вузол задовольняє наступним умовам: \begin{itemize} \item букви усіх вузлів лівого піддерева у алфавітному порядку йдуть перед буквеним позначенням поточного вузла, \item букви усіх вузлів правого піддерева у алфавітному порядку йдуть післе буквеного позначення поточного узла. \end{itemize} На рисунку показано приклад дерева, а також послідовність дій Антона. \includegraphics{https://static.e-olymp.com/content/72/7281c057249b22dfb9eb4697bf7ddbf166f9a9be.jpg} \InputFile Вхідний файл містить декілька рядків, у кожному з яких вказано рядок, що містить буквені позначення видалених вузлів. Останній рядок містить знак '\textbf{*}' - ознаку завершення рядків з даними. \OutputFile У вихідний файл виведіть рядок - структуру дерева у наступному порядку: \begin{itemize} \item якщо дерево порожнє, то і виведення порожнє, \item якщо дерево не порожнє, то виведіть дані у наступному порядку: \begin{itemize} \item дані кореневого вузла, \item дані лівого піддерева, \item дані правого піддерева. \end{itemize} \end{itemize} Якщо існує декілька розв'язків, Ви можете вивести довільний з них.