题目描述

在一条东西方向的道路上，有$A$座神社和$B$座寺庙。 从西边开始，第$i$座神社位于离道路西端$s_i$米处，第$i$座寺庙位于离道路西端$t_i$米处。

回答以下Q个查询:

第$i$个査询($1 <i< Q$):

如果我们从离道路西端$x_i$米的位置出发沿着道路自由行走，那么最小需要行走多少距离才能参观一座神社和一座寺庙?

(允许经过多于所需的神社和寺庙)

输入

第一行三个整数$A,B,Q$

接下来$A$行表示神庙的位置,接下来$B$行表示寺庙的位置。

输出

输出为$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

提示

$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_A \leq 10^{10}$

$1 \leq x_i \leq 10^{10}$

$s_1...s_A,t_1....t_B,x_1...x_q$均互不相同

输入均为整数

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