还原电报码

难度：T2

【知识点：前缀编码】【知识点：哈夫曼树】

前置知识：字符串、一维数组、循环、函数、树的路径

题目描述

接收方知道一张前缀编码表：不同字母的码字互不为前缀。收到一个完整的二进制位串，请把它还原为原来的大写字母串。每识别出一个字母，就从编码树的根重新开始。

输入格式

第一行整数 $n$。接下来 $n$ 行，每行一个大写字母和一个非空的 01 码字（仅由字符 0 与 1 组成），用空格隔开。最后一行是待解码位串。保证由该表完整编码而来，无残缺或非法位。

字母互不相同，码字互不为前缀，表的行顺序不限；输入字符串均无空格。

输出格式

输出一行解码后的大写字母串。

样例输入

4
C 001
A 1
B 01
D 000
1101001

样例输出

AABC

样例解释

位串切分为 1、1、01、001，依次对应 AABC。

数据范围

$2\le n\le26$，每个码字长度 $1$ 到 $20$，最后一行长度 $1$ 到 $2000$。