题目内容

给定一个从字符串到整数编号（$token-id$）的映射表，再给定一段由小写字母组成的文本。请把文本从左到右切分成若干个$token$：在当前位置，总是贪心地匹配能匹配到的最长 $token$，输出它的编号，然后从该$token$之后继续；如此重复，直到文本结束。

保证文本中出现的每个字符本身都是映射表中的一个 $token$（即所有必要的长度为$1$ 的$token$都存在），因此在任意位置贪心匹配总能成功，切分一定能覆盖整段文本。

输入描述

第一行包含一个整数$n(1≤n≤3×10^4)$，表示映射表中 $token$的数量。

接下来$n$ 行，每行包含一个 $token$字符串$t$ 和一个整数编号$id(0≤id≤10^9)$ ，中间用一个空格分隔。$t$ 由小写字母组成，长度不超过$12$ ，不同 $token$ 互不相同。

最后一行为待切分的文本$s$ ，由小写字母组成，长度为$M(1≤M≤10^5)$。

输出描述

输出切分得到的 $token$ 编号序列，用单个空格分隔，占一行。

样例1

输入

5
a 1
ab 2
abc 3
b 4
c 5
abcab

输出

3 2

说明

从位置$0$ 开始，能匹配的最长 $token$ 是 abc，输出编号$3$ ，前进到位置$3$ ；剩下的 ab 最长匹配是 ab，输出编号$2$ 。

样例2

输入

11
he 10
hell 11
hello 12
h 1
e 2
l 3
o 4
world 20
w 5
r 6
d 7
hellow

输出

12 5

说明

位置$0$ 处 he、hell、hello 都能匹配，贪心取最长的 hello，输出$12$ ；剩下的 w 只能匹配单字符 token w，输出$5$ 。