题目描述

由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理：将二叉树的空结点用“·”补齐（示例图未提供，核心规则为所有原本为空的左子树或右子树位置均用“·”标记）。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。

现给出扩展二叉树的先序序列，要求输出该扩展二叉树的中序序列和后序序列。

输入格式

输入仅一行，为扩展二叉树的先序序列（序列由字母和“·”组成，字母表示非空结点，“·”表示空结点，序列长度符合扩展二叉树的先序遍历规则）。

输出格式

输出共两行，第一行为扩展二叉树的中序序列，第二行为扩展二叉树的后序序列。

样例

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

DBFEGAC
DFGEBCA