题目描述

在我们超脑星球上，floyd 90 分钟跑不了 100 的数据范围，可能是因为超脑星球在一个黑洞旁边，导致其时间流速和地球差的很远。

从此时此刻起，忘记地球吧。我们脚下的这片土地的名字，叫做超脑星球。你们面前必须只能是星辰与大海。接下来就让我们一起来看看，在超脑星球上，到底有什么有趣迷人又刺激的事情会发生呢：

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，还有 $m$ 个整数 $b_1,b_2,\ldots,b_m$。

你要从这 $m$ 个整数中选出正好 $i$ 个，并将他们插入到序列 $a$ 中，注意不能插到头部或尾部。

同时需要满足，每对 $a_j$ 和 $a_{j+1}$ 之间，至多只插入了一个 $b$ 序列中的元素。

要求最大化新生成的序列中，相邻元素差的绝对值之和。

对于所有 $i$ 满足 $1\leq i\leq m$，均需输出答案。

输入格式

第一行两个整数 $n$ 和 $m$ 分别表示序列 $a$ 和序列 $b$ 的长度。

第二行 $n$ 个整数，表示序列 $a$ 的元素。

第三行 $m$ 个整数，表示序列 $b$ 的元素。

输出格式

输出一行 $m$ 个整数，第 $i$ 个表示恰好选取 $i$ 个时的答案。

样例 #1

样例输入 #1

10 8
2 25 29 2 28 20 24 8 30 27
13 21 17 18 14 30 9 23

样例输出 #1

169 193 205 217 223 223 223 223

提示

对于 $10\%$ 的数据，$n\leq 50$；

对于 $30\%$ 的数据，$n\leq 600$；

对于 $40\%$ 的数据，$n\leq 1000$；

对于 $60\%$ 的数据，$n\leq 5000$；

对于 $100\%$ 的数据，$1\leq m<n\leq 10^5,1\leq a_i,b_i\leq 10^8$。