题目描述

$Rubyonly$ 很喜欢园艺，他种出了一棵表达式树。

$Rubyonly$ 种出的这棵表达式树一共有 $n$ 个结点，并且是一棵二叉树。

每个结点上都有一个字符串 $a_i$ ，对于 $a_i$ 满足下面的性质：

如果 $i$ 是叶子结点，则 $a_i$ 的长度小于等于 $9$ ，字符集为 $\{\texttt{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\}$ ，且不存在前导零。
如果 $i$ 不是叶子节点，则 $a_i$ 的长度等于 $1$ ，字符集为 $\{\texttt{+, -, *, /}\}$ 。

$Rubyonly$ 想知道这棵表达式树对应的后缀表达式是怎样的，请你回答他。

输入格式

从文件 tree.in 中读入数据。

第一行一个正整数 $n$ ，表示树的结点数。

第二行 $n$ 个字符串，第 $i$ 个字符串表示 $a_i$ ，即结点 $i$ 上的字符串。

接下来 $n$ 行，每行两个整数 $u$ 和 $v$ ，分别表示结点 $i$ 的左儿子和右儿子编号。若 $u=0$ ，则表示结点 $i$ 不存在左儿子；同理，若 $v=0$ ，则表示结点 $i$ 不存在右儿子。

输出到文件 tree.out 中。

一行 $n$ 个字符串，表示这棵表达式树对应的后缀表达式，字符串之间用空格隔开。

3
865136873 + 149803736
0 0
1 3
0 0

865136873 149803736 +

对于全部数据，满足 $3\leq n\leq 2\times 10^5$ ， $0\leq u, v\leq n$ ，保证所有字符串 $a_i$ 的长度小于等于 $9$ 。