樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用。對(duì)于每一個(gè)結(jié)點(diǎn)至多只有兩課子樹的一類樹，稱其為二叉樹。二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一類重要的數(shù)據(jù)結(jié)構(gòu)，其形式定義如下：

而二叉樹的前序、中序遍歷是非常重要的能夠訪問二叉樹所有結(jié)點(diǎn)的算法，下面分別列出一種先序遍歷和兩種中序遍歷的算法。

第一種中序遍歷的方法（算法6.3）：

第二種中序遍歷的方法（算法6.2）：

通過讀入一個(gè)字符串，建立二叉樹的算法如下：

在本題中，將會(huì)給出一個(gè)按照先序遍歷得出的字符串，空格代表空的子節(jié)點(diǎn)，大寫字母代表節(jié)點(diǎn)內(nèi)容。請(qǐng)通過這個(gè)字符串建立二叉樹，并按照題目描述中的一種先序遍歷和兩種中序遍歷的算法分別輸出每一個(gè)非空節(jié)點(diǎn)。

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

共有三行，每一行包含一串字符，表示分別按先序、中序、中序得出的節(jié)點(diǎn)內(nèi)容，每個(gè)字母后輸出一個(gè)空格。請(qǐng)注意行尾輸出換行。