题目描述

将二叉树的每个空子树用字符 . 表示，按照先序次序描述整棵扩展二叉树。给出这个序列，求原二叉树的中序和后序遍历序列；输出时不包含表示空子树的 .。

输入格式

输入一行字符串，表示扩展二叉树的先序序列。

输出格式

输出两行，第一行为中序遍历，第二行为后序遍历。

样例

ABD..EF..G..C..

DBFEGAC
DFGEBCA

数据范围

实际结点数为 $1$ 至 $52$，结点用英文字母表示；输入保证是合法的扩展先序序列。