問題文
搜索命令 grep 有 有一个名为 -B 和 -A 的选项。这是
grep -B x -A y "needle" kakikomi.txt文件 带有kakikomi.txt 的模式 不仅是命中 "needle" 的行,而且就在该行之前。 x 行, 直後 y 这些行一起显示。紧接之前和之后的行数 如果小于x,y,则显示尽可能多的内容。
如果具有相同行号的行多次出现,它们将被合并,以便每行仅出现一次。输出示例中详细解释了此行为。
现在文件 具有kakikomi.txt 的特定模式 运行grep和要命中的行号列表 假设 L_1,L_2,...,L_n 已知。这里 给出 m 查询,并分别指定x和y。对于每个查询, 同样,添加选项-B x -A y如果执行grep,请回答显示的行数。 表示
入力
all N M
L_{1}
L_{2}
:
L_{N}
x_{1} y_{1}
x_{2} y_{2}
:
x_{M} y_{M}
- 1 在线 kakikomi.txt 中的行数的整数 all(1≦all≦10^9),表示命中的行数的整数 N(1≦N≦min(all,10^5)) ,查询 表示x, y 数量的整数 直到 M(1≦M≦10^5) 给出。
- 2 从行 N+1 行 在 N 行中, 一个整数,表示i 命中行的行号 一个整数,表示 L_{i}(1≦L_{i}≦all) 给出。
- L_i 为 L_i < L_{i+1}符合。
- N+2 从行 N+M+1 行 在 M 行中, 一个整数,表示L_i 的每个查询 x_i, y_i(0≦x_i, y_i≦10^9) 给出。
出力
另外,在输出末尾放置一个换行符。
入力例 1
7 2 3 2 4 1 1 3 0 3 4
出力例 1
5 4 7
- 命中线是 2 线和 这是 4 行。
- x = 1, y = 1 ,每个命中范围是 1 ~ 3 行目、3 ~ 5 行,所以匹配 5行就是答案。
- x = 3, y = 0 ,每个命中范围是 1 ~ 2 行目、1 ~ 4 行,所以匹配 4行就是答案。
- x = 3, y = 4 ,每个命中范围是 1 ~ 6 行目、1 ~ 7 行,所以匹配 7行就是答案。
入力例 2
100 5 5 3 18 24 57 90 1 8 27 0 15 16 22 3 2 2
出力例 2
46 80 98 79 25