题目描述

一条笔直道路上有 $n$ 个服务站，整数坐标 $a_1,a_2,\ldots,a_n$ 已经按严格递增顺序给出。两个坐标 $u,v$ 之间的距离为 $|u-v|$。

每次给出一位居民的整数坐标 $x$，请输出离他最近的服务站坐标。如果有两个服务站距离相同，选择坐标较小的一个。

至少有一个服务站。查询不会改变服务站位置，坐标可以为负数。

输入格式

第一行包含两个整数 $n,q$，表示服务站数量和查询次数。

第二行包含 $n$ 个严格递增的整数坐标。

接下来 $q$ 行，每行包含一个整数 $x$，表示居民坐标。

输出格式

输出 $q$ 行，每行一个整数，表示所选服务站的坐标。

3 5
2 8 14
11
12
1
20
8

8
14
2
14
8

1 3
-1000000000000
-1000000000000
0
1000000000000

-1000000000000
-1000000000000
-1000000000000

样例 1 解释

居民位于 11 时，到 8 和 14 的距离都是 3，选择较小坐标 8；位于 12 时选择 14。居民在所有站点左侧或右侧时，选择对应端点。

样例 2 解释

只有一个服务站，三次查询都选择它。注意输出的是坐标，不是下标。

数据范围与提示

对于所有数据，$1\le n,q\le 200000$，$-10^{12}\le a_i,x\le 10^{12}$。保证服务站坐标严格递增。

共 $20$ 个测试点，每个测试点 $5$ 分，按测试点独立计分，总分 $100$ 分。

测试点	规模限制
1—5	$n,q\le 20$
6—10	$n,q\le 2000$
11—15	$n,q\le 50000$
16—20	$n,q\le 200000$

表中的规模限制只限制对应参数的上界，所有测试点同时满足上述完整数据范围。

时间限制：2 秒。内存限制：128 MiB。