T9

휴대폰으로 문자 메시지를 쓸 때 널리 쓰는 T9 입력 방식을 구현한다.

숫자 버튼에는 영문 소문자가 다음과 같이 배정되어 있다.

단어를 입력할 때는 글자마다 그 글자가 배정된 버튼을 한 번씩만 누른다. 버튼에 문자가 몇 개 배정되어 있는지, 그 글자가 버튼에서 몇 번째인지는 상관없다. 소프트웨어는 눌린 버튼 순서에 맞는 단어를 사전에서 골라 화면에 보여준다. 맞는 단어가 여럿이면 빈도가 큰 단어를 먼저 보여주고, 빈도가 같은 단어는 처음에는 사전순으로 보여준다.

보여준 단어가 원하는 단어가 아니면 사용자는 * 버튼을 누른다. 그러면 같은 버튼 순서에 맞는 단어 중 다음 순서의 단어가 나온다. 그 단어도 아니면 *를 다시 누른다. 요즘 휴대폰에는 필요한 단어가 모두 들어 있는 사전이 있다고 보고, 필요한 단어는 항상 찾을 수 있다고 가정한다.

보여준 단어가 맞으면 사용자는 space를 누르거나, 문장 부호에 해당하는 1을 누르거나, 입력을 끝낼 수 있다. 나온 문장 부호가 원하는 것이 아니면 맞는 문자가 나올 때까지 *를 누른다. 문장 부호는 세 개면 충분하고 ., ,, ? 순서로 제시된다. space나 문장 부호를 입력한 뒤에는 space나 문장 부호를 다시 입력해도 되고, 입력을 끝내도 되고, 다음 단어를 입력해도 된다.

사용자가 space나 1을 눌러 단어를 확정하면 그 단어의 빈도가 1 늘어나고, 늘어난 빈도는 그 뒤에 입력하는 단어부터 적용된다. 또 그 단어는 같은 빈도인 단어 중 가장 먼저 제시되며, 나머지 단어끼리의 순서는 바뀌지 않는다. 나중에 다른 단어가 같은 빈도가 되면 그 단어가 그 빈도 안에서 가장 먼저 제시되고, 나머지 순서는 그대로 남는다.

2부터 9까지의 버튼은 지금 입력하고 있는 단어의 버튼 순서 뒤에 붙는다. 버튼이 하나 늘어나면 새 버튼 순서에 맞는 첫 번째 후보부터 다시 보여준다. 입력이 끝난 순간 화면에 남아 있는 단어나 문장 부호도 메시지에 들어간다. 다만 space나 1로 확정하지 않은 단어의 빈도는 늘어나지 않는다.

단어별 초기 빈도가 적힌 사전과 사용자가 누른 버튼 순서가 주어진다. 화면에 나타나는 메시지를 출력하는 프로그램을 작성한다.

첫째 줄에 사전에 있는 단어의 개수 $N$ ($3 \le N \le 50000$)이 주어진다. 다음 $N$개 줄에는 각각 사전의 단어 하나와 그 단어의 초기 빈도 $F$ ($1 \le F \le 1000$)가 주어진다. $F$가 클수록 빈도가 높다. 단어와 빈도는 공백 하나로 구분된다. 단어는 영문 소문자로만 이루어지고 길이는 20자를 넘지 않으며, 비어 있지 않고 서로 다르다. 입력의 단어는 사전순으로 정렬되어 있다.

마지막 줄에는 메시지를 입력하면서 누른 버튼의 순서를 나타내는 문자열이 주어진다. 이 문자열은 숫자 1부터 9까지, space, *로만 이루어지고 길이는 100000자를 넘지 않는다.

화면에 나타난 문자 메시지를 출력한다.

두 번째 예제에서 소프트웨어는 처음에 act를 제시하고 그다음 bat을 제시하며, 사용자는 bat을 확정한다. 그러면 bat의 빈도가 2가 되므로 같은 숫자 조합을 다시 입력하면 bat, act, cat 순으로 제시된다. 세 번째로 입력할 때는 빈도가 막 2가 된 cat이 먼저 나오고, 그다음 빈도가 2인 bat, 그다음 act가 나온다. 이때 act의 빈도도 다른 단어와 같아진다. 마지막에는 act, cat, bat 순으로 제시된다.