题目描述

東西方向に伸びる道路に沿って $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$ への答えを出力すること。

题目大意

一条东西向的道路有$A$家神社和$B$家寺庙。以道路最西面为坐标$0$点，第$i$家神社位于坐标$s_i$ ，第$j$家寺庙位于坐标$t_j$处。

你需要回答以下$Q$个询问： 询问$k$：从坐标$x_k$出发，要至少访问一家神社和一家寺庙，最少需要移动多少距离？

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

350
1400
301
399

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_B\ \leq\ 10^{10} $
• $1\ \leq\ x_i\ \leq\ 10^{10}$
• $ s_1,\ ...,\ s_A,\ t_1,\ ...,\ t_B,\ x_1,\ ...,\ x_Q $ はすべて異なる。
• 入力される値はすべて整数である。

Sample Explanation 1

$2$ 社の神社と $3$ 軒の寺があり、神社は道路の西端から $100,\ 600$ メートルの地点に、寺は道路の西端から $400,\ 900,\ 1000$ メートルの地点にあります。 - 問 $1$: 道路の西端から $150$ メートルの地点から出発する場合、まず西に $50$ メートル進んで神社を訪れ、次に東に $300$ メートル進んで寺を訪れるのが最適です。 - 問 $2$: 道路の西端から $2000$ メートルの地点から出発する場合、まず西に $1000$ メートル進んで寺を訪れ、次に西に $400$ メートル進んで神社を訪れるのが最適です。途中で寺をもう一軒通過しますが、構いません。 - 問 $3$: 道路の西端から $899$ メートルの地点から出発する場合、まず東に $1$ メートル進んで寺を訪れ、次に西に $300$ メートル進んで神社を訪れるのが最適です。 - 問 $4$: 道路の西端から $799$ メートルの地点から出発する場合、まず西に $199$ メートル進んで神社を訪れ、次に西に $200$ メートル進んで寺を訪れるのが最適です。

Sample Explanation 2

道路は長く、$32$ ビット整数に収まらない距離を移動する必要があるかもしれません。