第一个及格的学生

题目描述

某次考试结束后，共有 (n) 名学生参加成绩登记。

每名学生有一个由英文字母组成的姓名和一个整数成绩。系统会先按照以下规则对所有学生进行排序：

1. 成绩较低的学生排在前面；
2. 如果两名学生的成绩相同，则姓名字典序较小的学生排在前面。

排序完成后，系统将处理 (q) 次查询。

每次查询给出一个整数 (x)，表示本次查询的及格分数线。请输出排序后的学生序列中，第一个成绩不低于 (x) 的学生姓名。

注意，这名学生的成绩不一定恰好等于 (x)。

如果不存在成绩不低于 (x) 的学生，则输出：

None

---

输入格式

第一行包含两个整数 (n,q)，分别表示学生人数和查询次数。

接下来 (n) 行，每行包含一个字符串 name 和一个整数 score，分别表示一名学生的姓名和成绩。

接下来 (q) 行，每行包含一个整数 (x)，表示一次查询的及格分数线。

---

输出格式

对于每次查询，输出一行。

• 如果存在成绩不低于 (x) 的学生，输出排序后第一个符合条件的学生姓名；
• 否则输出 None。

---

数据范围

对于所有测试数据：

$1\le n,q\le 2\times 10^5$

$0\le score\le 10^9$

$0\le x\le 10^9$

学生姓名仅包含大小写英文字母，长度不超过 (20)。

所有学生姓名互不相同。

字符串按照 C++ 默认字典序进行比较，且大小写敏感。

---

样例输入 1

5 4
Tom 78
Alice 92
Bob 60
David 78
Cindy 85
70
78
90
100

样例输出 1

David
David
Alice
None

---

样例解释 1

按照题目规则排序后，学生顺序为：

Bob 60
David 78
Tom 78
Cindy 85
Alice 92

对于查询 (70)：

• Bob 的成绩为 (60)，不满足要求；
• David 的成绩为 (78)，是第一个成绩不低于 (70) 的学生。

因此输出：

David

对于查询 (78)：

成绩为 (78) 的学生有：

David
Tom

由于 David 的字典序小于 Tom，所以 David 排在前面，输出：

David

对于查询 (90)：

序列中第一个成绩不低于 (90) 的学生是成绩为 (92) 的 Alice。

注意，虽然没有学生的成绩恰好为 (90)，但仍然存在成绩不低于 (90) 的学生。

对于查询 (100)：

所有学生的成绩都低于 (100)，因此输出：

None

---

样例输入 2

8 6
Zoe 70
Amy 70
Mike 90
Jack 80
Bob 60
Lily 80
Cindy 70
Eric 95
59
60
69
70
71
96

样例输出 2

Bob
Bob
Amy
Amy
Jack
None

---

样例解释 2

排序后的学生序列为：

Bob 60
Amy 70
Cindy 70
Zoe 70
Jack 80
Lily 80
Mike 90
Eric 95

对于查询 (69)，第一个成绩不低于 (69) 的学生是 Amy，而不是 Bob。

对于查询 (71)，成绩为 (70) 的学生都不满足要求，因此答案是成绩为 (80) 的 Jack。