题目描述

给定一棵二叉树的扩展后序序列,其中 . 表示空节点，试构造这个二叉树，并输出这个二叉树的先序遍历结果。

输入格式

一行字符，即扩展后序序列，字符只包含小写字母和 .，长度不超过 $255$

输出格式

输出对应的先序遍历结果。

..a..bc.d

dcab

样例 1 解释

根据扩展后序得到的二叉树:

数据规模与约定

对于 $100\%$ 的数据，字符只包含小写字母和 .，且长度不超过 $255$