题目描述

给出一些单词和其对应的页码。若某个单词出现多次，则只保留第一次出现的那一对（即第一对有效）。

现在需要查询若干单词是否存在于该字典中：

• 若存在，输出对应的页码；
• 若不存在，输出 -1。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示单词数量和查询数量（$1 \le n, m \le 100000$）。

接下来 $n$ 行，每行包含一个单词和一个整数，表示单词及其对应的页码。
若同一个单词出现多次，则仅第一次出现有效。

接下来 $m$ 行，每行一个单词，表示要查询的单词。

输出格式

输出 $m$ 行，每行对应一个查询结果：

• 若单词存在，输出其页码；
• 否则输出 -1。

输入输出样例

输入

5 5
aa 1
bb 2
cc 3
dd 4
aa 5
aa
bb
cc
dd
ee

输出

1
2
3
4
-1

说明

对于单词 aa：

• 第一次出现为 aa 1
• 第二次出现为 aa 5

由于本题规定“第一对有效”，因此查询 aa 时输出 1。

数据范围

• $1 \le n, m \le 100000$
• 单词由可见字符组成（不包含空格）
• 页码为整数