#ABC119D. 懒惰的信徒
懒惰的信徒
AT_abc119_d [ABC119D] Lazy Faith
题目描述
在一条东西方向延伸的道路旁,沿路建有 家神社和 座寺庙。从西端起第 家神社位于距离道路西端 米处,从西端起第 座寺庙位于距离道路西端 米处。
请回答以下 个问题。
第 个问题():如果从距离道路西端 米的地点出发,并可以在道路上自由移动,访问一座神社和一座寺庙所需的最小移动距离是多少米?(途中可以经过多于一座神社或寺庙也没有关系。)
输入格式
第一行输入三个整数 $a, b, q \left(1 \leqq a, b \leqq 10^5;\ 1 \leqq q \leqq 10^5\right)$ 代表神社数量、寺庙数量和问题数量。
第二行输入 个整数 $s_1, s_2, \dots, s_a \left(1 \leqq s_1 < s_2 < \dots < s_a \leqq 10^{10}\right)$ 代表每家神社到道路西端的距离。
第三行输入 个整数 $t_1, t_2, \dots, t_b \left(1 \leqq t_1 < t_2 < \dots < t_b \leqq 10^{10}\right)$ 代表每座寺庙到道路西端的距离。
第四行输入 个整数 $x_1, x_2, \dots, x_q \left(1 \leqq x_i \leqq 10^{10}\right)$ 代表每个问题的出发地点到道路西端的距离。
保证 $s_1, s_2, \dots, s_a, t_1, t_2, \dots, t_b, x_1, x_2, \dots, x_q$ 两两互不相同。
输入中的所有整数之间只用空白字符(空格或换行)分隔,行数不固定,按顺序读取这些整数即可。
输出格式
输出 行,第 行输出一个整数,代表第 个问题的答案。
测试样例
2 3 4
100 600
400 900 1000
150 2000 899 799
350
1400
301
399
样例 1 解释
有 家神社和 座寺庙,神社分别位于距离西端 米处,寺庙分别位于 米处。
问题 :从距离西端 米处出发,最优方案是先向西走 米到神社,再向东走 米到寺庙;
问题 :从距离西端 米处出发,最优方案是先向西走 米到寺庙,再向西走 米到神社。途中会经过一座寺庙,但没有关系;
问题 :从距离西端 米处出发,最优方案是先向东走 米到寺庙,再向西走 米到神社;
问题 :从距离西端 米处出发,最优方案是先向西走 米到神社,再向西走 米到寺庙。
1 1 3
1
10000000000
2 9999999999 5000000000
10000000000
10000000000
14999999998
样例 2 解释
道路很长,可能需要移动的距离会超过 位整数的范围。