新年参拜

题目描述

沿东西方向延伸的道路旁,建有 $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$ 行输出问题 $i$ 的答案。

样例

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

350
1400
301
399

有 $2$ 座神社和 $3$ 座寺庙,神社位于距道路西端 $100, 600$ 米处,寺庙位于距道路西端 $400, 900, 1000$ 米处。

• 问题 $1$: 从距道路西端 $150$ 米处出发时,先向西走 $50$ 米访问神社,再向东走 $300$ 米访问寺庙是最优的。
• 问题 $2$: 从距道路西端 $2000$ 米处出发时,先向西走 $1000$ 米访问寺庙,再向西走 $400$ 米访问神社是最优的。途中经过另一座寺庙,但没有关系。
• 问题 $3$: 从距道路西端 $899$ 米处出发时,先向东走 $1$ 米访问寺庙,再向西走 $300$ 米访问神社是最优的。
• 问题 $4$: 从距道路西端 $799$ 米处出发时,先向西走 $199$ 米访问神社,再向西走 $200$ 米访问寺庙是最优的。

1 1 3
1
10000000000
2
9999999999
5000000000

10000000000
10000000000
14999999998

道路很长,可能需要移动 $32$ 位整数无法容纳的距离。

数据范围

• $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$ 互不相同。
• 输入的所有值均为整数。