Катя решила разместить на стене своей комнаты свое собственное родословное дерево. Родословное дерево строится просто: \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} Если существует несколько решений, Вы можете вывести любое из них.