题目描述

Along a road running in an east-west direction, there are $A$ shrines and $B$ temples. The $i$-th shrine from the west is located at a distance of $s_i$ meters from the west end of the road, and the $i$-th temple from the west is located at a distance of $t_i$ meters from the west end of the road.

Answer the following $Q$ queries:

• Query $i$ ($1 \leq i \leq Q$): If we start from a point at a distance of $x_i$ meters from the west end of the road and freely travel along the road, what is the minimum distance that needs to be traveled in order to visit one shrine and one temple? (It is allowed to pass by more shrines and temples than required.)

在一条东西走向的道路上，有 $A$ 座神社和 $B$ 座寺庙。西面的 $i$ 个神龛距离道路西端 $s_i$ 米，西面的 $i$ 个寺庙距离道路西端 $t_i$ 米。

请回答下列 $Q$ 个问题：

• 查询 $i$ ( $1 \leq i \leq Q$ )：如果我们从距离道路西端 $x_i$ 米的地方出发，沿着道路自由行进，那么参观一个神社和一座寺庙至少需要走多少路程？(允许经过的神社和寺庙比要求的多）。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印 $Q$ 行。 $i$ -th 行应包含 $i$ -th 查询的答案。

样例 #1

样例输入 #1

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

样例输出 #1

350
1400
301
399

样例 #2

样例输入 #2

1 1 3
1
10000000000
2
9999999999
5000000000

样例输出 #2

10000000000
10000000000
14999999998

说明

数据规模与约定

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

样例 $1$ 解释

有两座神社和三座寺庙。神社距离道路西端 $100, 600$ 米，寺庙距离道路西端 $400, 900, 1000$ 米。

• 问题 $1$ ：如果我们从距离道路西端 $150$ 米的地方出发，最优的行动是先向西行走 $50$ 米去参拜神社，然后向东走 $300$ 米去参拜寺庙。
• 问题 $2$ ：如果我们从距离道路西端 $2000$ 米的地方出发，最佳路线是先向西行走 $1000$ 米参观一座寺庙，然后再向西行走 $400$ 米参观一座神庙。途中我们会经过另一座寺庙，但这并没有问题。
• 问题 $3$ ：如果我们从距离道路西端 $899$ 米的地方出发，最佳行动是先向东走 $1$ 米去拜访一座寺庙，然后再向西走 $300$ 米去拜访一座神庙。
• 问题 $4$ ：如果我们从距离道路西端 $799$ 米的地方出发，最佳移动是先向西行走 $199$ 米去参拜神庙，然后再向西行走 $200$ 米去参拜寺庙。

样例 $2$ 解释

这条路相当长，我们可能需要走的距离并不适合 $32$ （位）整数。