//蒟蒻的第二篇题解

问题描述

你从融侨山区考入大城市沙坪坝的学校，但是沙坪坝的当地人说着一种很难懂的方言，你完全听不懂。幸好你手中有本字典可以帮你。现在你有若干个听不懂的方言需要查询字典。

输入格式

第一行，两个整数n和m。 接下来有n行表示字典的内容，每行表示一条字典的记录。每条记录包含两个空格间隔的单词，第一个单词为英文单词，第二个单词为对应的沙坪坝方言。 接下来有m行，每行一个单词，表示你要查询的沙坪坝方言。

输出格式

输出m行，每行一个英文单词，表示翻译后的结果。 如果某个单词字典查不到，输出"eh"

样例输入

5 3 dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay

样例输出

cat eh loops

重要的事情说三遍：不要用cin 不要用cin 不要用cin！！！

题目大意 输入𝑛条英文单词和方言单词的对应关系，然后进行𝑚次查询，每次查询一个方言单词对应的英文 单词。数据范围𝑛, 𝑚 ≤ 100000，单词长度不超过10。

解析

• 将𝑛条对应关系按方言单词的字典序排序，然后二分查找。