D - 懒惰的信仰

得分：400

问题描述

在一条东西方向的道路上，有$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$个查询的答案。

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

350
1400
301
399

有两座神社和三座寺庙。神社分别位于离道路西端$100$米和$600$米处，寺庙分别位于离道路西端$400$、$900$和$1000$米处。

• 第一个查询：如果我们从离道路西端$150$米的位置出发，最优行动是向西走$50$米去参拜一座神社，然后向东走$300$米去参拜一座寺庙。
• 第二个查询：如果我们从离道路西端$2000$米的位置出发，最优行动是向西走$1000$米去参拜一座寺庙，然后向西走$400$米去参拜一座神社。路上还会经过另一座寺庙，但这没关系。
• 第三个查询：如果我们从离道路西端$899$米的位置出发，最优行动是向东走$1$米去参拜一座寺庙，然后向西走$300$米去参拜一座神社。
• 第四个查询：如果我们从离道路西端$799$米的位置出发，最优行动是向西走$199$米去参拜一座神社，然后向西走$200$米去参拜一座寺庙。

1 1 3
1
10000000000
2
9999999999
5000000000

10000000000
10000000000
14999999998

道路很长，我们可能需要行走的距离无法放入一个$32$位整数中。