题目描述

给定一棵二叉树的扩展后序序列，试构造这个二叉树，并输出这个二叉树的前序遍历结果。

输入

一行字符，即扩展后序序列

输出

输出对应的前序遍历结果

样例

..a..b.cd

dacb