配点 : $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

$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$ ビット整数に収まらない距離を移動する必要があるかもしれません。