题目描述

沿着一条东西方向的道路上，有 $A$ 个神社和 $B$ 个寺庙。从道路西端起，第 $i$ 个神社位于距离西端 $s_i$ 米的位置，第 $i$ 个寺庙位于距离西端 $t_i$ 米的位置。

回答以下 $Q$ 个查询：

• 查询 $i$ ($1 \leq i \leq Q$)：如果我们从距离西端 $x_i$ 米的位置出发，在道路上自由行进，那么需要行进的最小距离是多少，以便访问一个神社和一个寺庙？（允许经过的神社和寺庙多于所需的数量。）

约束条件

• $1 \leq A, B \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq s_1 < s_2 < ... < s_A \leq 10^{10}$
• $1 \leq t_1 < t_2 < ... < t_B \leq 10^{10}$
• $1 \leq x_i \leq 10^{10}$
• $s_1, ..., s_A, t_1, ..., t_B, x_1, ..., x_Q$ 均不相同。
• 输入中的所有值均为整数。

输入

从标准输入读取数据，具体格式如下：

$A$ $B$ $Q$ $s_1$ : $s_A$ $t_1$ : $t_B$ $x_1$ : $x_Q$

输出

打印 $Q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案。

示例输入 1

2 3 4
100
600
400
900
1000
150
2000
899
799

示例输出 1

350
1400
301
399

这里有两个神社和三个寺庙。神社位于距离道路西端 $100, 600$ 米的位置，而寺庙位于距离道路西端 $400, 900, 1000$ 米的位置。

• 查询 $1$：如果我们从距离道路西端 $150$ 米的位置出发，最佳移动方式是先向西走 $50$ 米访问一个神社，然后向东走 $300$ 米访问一个寺庙。
• 查询 $2$：如果我们从距离道路西端 $2000$ 米的位置出发，最佳移动方式是先向西走 $1000$ 米访问一个寺庙，然后向西走 $400$ 米访问一个神社。在途中我们会经过另一个寺庙，但没关系。
• 查询 $3$：如果我们从距离道路西端 $899$ 米的位置出发，最佳移动方式是先向东走 $1$ 米访问一个寺庙，然后向西走 $300$ 米访问一个神社。
• 查询 $4$：如果我们从距离道路西端 $799$ 米的位置出发，最佳移动方式是先向西走 $199$ 米访问一个神社，然后向西走 $200$ 米访问一个寺庙。

示例输入 2

1 1 3
1
10000000000
2
9999999999
5000000000

示例输出 2

10000000000
10000000000
14999999998

这条道路很长，我们可能需要行进的距离无法适应 $32$ 位整数。