在遍歷二叉樹的過程中，是按照一定的規(guī)則將二叉樹中的結(jié)點排列成一個線性序列，從而得到二叉樹中結(jié)點的先序序列或中序序列或后序序列。但是，當(dāng)以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到結(jié)點的左右孩子信息，而不能直接得到結(jié)點在任意一個序列中的前驅(qū)和后繼的信息，而這種信息只有在遍歷的動態(tài)過程中才能夠得到。

為了保存這種信息，就需要使用線索鏈表。其中指向結(jié)點的前驅(qū)和后繼的指針，叫做線索。添加上線索的二叉樹稱之為線索二叉樹。其結(jié)點定義如下：

下面給出按照中序遍歷將二叉樹中序線索化的算法：

在已經(jīng)線索化的二叉線索樹中，進行中序遍歷的算法如下所示：

本題中，將會給出一個按照先序遍歷得出的字符串，空格代表空的子節(jié)點，大寫字母代表節(jié)點內(nèi)容。請通過這個字符串建立二叉樹，并按照題目描述中算法，中序遍歷二叉樹并中序線索化二叉樹，之后中序遍歷輸出二叉線索樹。

輸入只有一行，包含一個字符串S，用來建立二叉樹。保證S為合法的二叉樹先序遍歷字符串，節(jié)點內(nèi)容只有大寫字母，且S的長度不超過100。

共一行，包含一串字符，表示按中序遍歷二叉線索樹得出的節(jié)點內(nèi)容，每個字母后輸出一個空格。請注意行尾輸出換行。