分数: 366 分
问题陈述
高桥经营一家网上商店并负责 N 产品。产品编号为 1 to N和产品 i (1 \leq i \leq N) 的名称 S_i 和价格 V_i 日元。不同的产品可能具有相同的名称或相同的价格。
青木是这家店的顾客,已发送 Q 搜索请求。在 j第一个请求 (1 \leq j \leq Q),他指定一个整数 X_j 并询问:“请告诉我所有价格准确的产品 X_j 日元。”
然而,青木可能不记得确切的价格。因此,为了青木的方便,高桥决定按照以下规则返回搜索结果:
- 如果存在一种或多种产品,其价格恰好为 X_j 日元,产量 全部 其名称位于一行,以空格分隔,按产品编号升序排列。即使多个匹配产品具有相同的名称,每个产品也会作为单独的产品输出一次(这意味着名称可能会在输出中出现重复)。
- 如果没有产品的价格恰好为 X_j 日元,作为“您指的是该产品吗?”的建议,选择并输出价格最接近的一种产品 X_j。具体来说,候选者是使绝对差异最小化的产品 |V_i - X_j|。如果有多个候选产品(例如,一种产品同样便宜,另一种产品同样昂贵) X_j),选择其中产品编号最小的一个。输出 只有一个 单行中所选产品的名称。
确定每个请求的搜索结果。
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- S_i 是长度介于 1 和 20 包含在内,仅由小写英文字母组成。
- 1 \leq V_i \leq 10^9
- 1 \leq X_j \leq 10^9
- N, Q, V_i, X_j 均为整数。
- 保证所有请求输出的产品名称总字符数(不包括分隔空格和换行符)不超过 10^6.
输入
N Q S_1 V_1 S_2 V_2 \vdots S_N V_N X_1 X_2 \vdots X_Q
- 第一行包含产品数量 N 和搜索请求数 Q,用空格分隔。
- 的 i- 以下各项 N 行 (1 \leq i \leq N) 包含字符串 S_i 代表产品名称 i 和整数 V_i 代表其价格,以空格分隔。
- 的 j- 以下各项 Q 行包含价格 X_j 中指定 j第一个搜索请求。
输出
对于每个 Q 搜索请求,输出一行。
- 如果存在一种或多种产品,其价格恰好为 X_j 日元,按产品编号升序输出其名称,以空格分隔。即使多个匹配产品具有相同的名称,也将每个产品输出为单独的产品。
- 如果没有产品的价格恰好为 X_j 日元,仅输出最小化的产品中产品编号最小的产品名称 |V_i - X_j|.
示例输入 1
5 4 apple 100 banana 200 cherry 100 date 300 elderberry 500 100 250 300 150
示例输出 1
apple cherry banana date apple
示例输入 2
4 5 milk 150 bread 150 cheese 300 butter 300 150 300 200 225 450
示例输出 2
milk bread cheese butter milk milk cheese
示例输入 3
10 8 notebook 1200 pen 300 eraser 100 ruler 500 pencil 300 marker 800 tape 250 glue 250 scissors 1500 stapler 1200 300 1200 100 700 2000 1 250 999
示例输出 3
pen pencil notebook stapler eraser marker scissors eraser tape glue marker
示例输入 4
15 10 alpha 1000 beta 2000 gamma 3000 delta 4000 epsilon 5000 zeta 6000 eta 7000 theta 8000 iota 9000 kappa 10000 lambda 1000 mu 5000 nu 5000 xi 15000 omicron 20000 5000 1000 7500 1 1000000000 10000 15000 12000 20000 3500
示例输出 4
epsilon mu nu alpha lambda eta alpha omicron kappa xi kappa omicron gamma
示例输入 5
1 1 a 1000000000 1000000000
示例输出 5
a