题目描述

为了加密单词，小可将26个大写字母，每个大写字母存储在一个二叉树的节点中。

加密时，将每个字母替换为对应的节点编号。节点的编号规则如下：

• 根节点编号为 0。

• 若某节点编号为 p，则其左子节点编号为 2p + 1，右子节点编号为 2p + 2。

现给出每个字母的父节点信息和位置，以及要加密的单词，请输出加密后的编号序列。

输入格式

前 $26$ 行，为密码信息，每行格式为val fa dir

• val：当前结点存储的大写字母
• fa：当前结点的父结点编号
• dir：当前结点在父结点下的位置（$1$ 表示左子结点， $2$ 表示右子结点）

特别的：对于根结点，$fa$ 和 $dir$ 为 $-1$。

• 最后一行：待加密的单词（长度不超过 $1000$）。

输出格式

输出单词加密结果。

样例

K -1 -1
D 0 1
E 0 2
A 1 1
B 1 2
C 2 1
F 2 2
G 3 1
H 3 2
I 4 1
J 4 2
L 5 1
M 5 2
N 6 1
O 6 2
P 7 1
Q 7 2
R 8 1
S 8 2
T 9 1
U 9 2
V 10 1
W 10 2
X 11 1
Y 11 2
Z 12 1
KEDAAC

0 2 1 3 3 5