Capture a string containing the input data. Build an AVL (height balanced) binary search tree. That is, the one in which the difference between the heights of the left branch and the right branch of each of its records does not differ by more than one unit. Record the (unordered) text in the binary tree in ordered form and show its inorder, preorder, and postorder traversals.

Input

Letters that will form a node in the binary (sorted) tree.

Output

• Inorder traversal of the binary tree.
• Preorder traversal of the binary tree.
• Postorder traversal of the binary tree.

Example

Input:
GKILQMT

Output:
GIKLMQT
LIGKQMT
GKIMTQL

Capturar un string que contiene los datos de entrada. Construir un árbol binario de búsqueda AVL( balanceado por la altura). Es decir aquel en que la diferencia entre las alturas de la rama izquierda y la rama derecha de cada uno de sus registros no difiere en más de una unidad. Registrar en el árbol binario el texto (desordenado) en forma ordenada y mostrar sus recorridos inorden, preorden y posorden.

Input

Letras que formarán un nodo en el árbol binario (ordenado).

Output

Recorrido inorden del árbol binario.

Recorrido preorden del árbol binario.

Recorrido posorden del árbol binario.

Example

Input:
GKILQMT

Output:
GIKLMQT
LIGKQMT
GKIMTQL