题目描述

由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树的空结点用 . 补齐，记为扩展二叉树。

现给出扩展二叉树的先序遍历序列（空结点用 . 表示），要求输出该二叉树的中序和后序遍历序列。

输入格式

一行，一个字符串，表示扩展二叉树的先序遍历序列。

输出格式

第一行：中序遍历序列
第二行：后序遍历序列

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

DBFEGAC
DFGEBCA

数据规模与约定

对于全部的测试点，保证输入字符串长度不超过 $100$，且只包含大写字母和 .，能唯一确定一棵扩展二叉树。