/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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 への答えを出力すること。
入力例 1
2 3 4 100 600 400 900 1000 150 2000 899 799
出力例 1
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 メートル進んで寺を訪れるのが最適です。
入力例 2
1 1 3 1 10000000000 2 9999999999 5000000000
出力例 2
10000000000 10000000000 14999999998
道路は長く、32 ビット整数に収まらない距離を移動する必要があるかもしれません。
Score : 400 points
Problem Statement
Along a road running in an east-west direction, there are A shrines and B temples. The i-th shrine from the west is located at a distance of s_i meters from the west end of the road, and the i-th temple from the west is located at a distance of t_i meters from the west end of the road.
Answer the following Q queries:
- Query i (1 \leq i \leq Q): If we start from a point at a distance of x_i meters from the west end of the road and freely travel along the road, what is the minimum distance that needs to be traveled in order to visit one shrine and one temple? (It is allowed to pass by more shrines and temples than required.)
Constraints
- 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 are all different.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B Q s_1 : s_A t_1 : t_B x_1 : x_Q
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
2 3 4 100 600 400 900 1000 150 2000 899 799
Sample Output 1
350 1400 301 399
There are two shrines and three temples. The shrines are located at distances of 100, 600 meters from the west end of the road, and the temples are located at distances of 400, 900, 1000 meters from the west end of the road.
- Query 1: If we start from a point at a distance of 150 meters from the west end of the road, the optimal move is first to walk 50 meters west to visit a shrine, then to walk 300 meters east to visit a temple.
- Query 2: If we start from a point at a distance of 2000 meters from the west end of the road, the optimal move is first to walk 1000 meters west to visit a temple, then to walk 400 meters west to visit a shrine. We will pass by another temple on the way, but it is fine.
- Query 3: If we start from a point at a distance of 899 meters from the west end of the road, the optimal move is first to walk 1 meter east to visit a temple, then to walk 300 meters west to visit a shrine.
- Query 4: If we start from a point at a distance of 799 meters from the west end of the road, the optimal move is first to walk 199 meters west to visit a shrine, then to walk 200 meters west to visit a temple.
Sample Input 2
1 1 3 1 10000000000 2 9999999999 5000000000
Sample Output 2
10000000000 10000000000 14999999998
The road is quite long, and we may need to travel a distance that does not fit into a 32-bit integer.