#ABC119D. 懒惰的信徒

懒惰的信徒

AT_abc119_d [ABC119D] Lazy Faith

题目描述

\hspace{15pt}在一条东西方向延伸的道路旁,沿路建有 aa 家神社和 bb 座寺庙。从西端起第 ii 家神社位于距离道路西端 sis_i 米处,从西端起第 ii 座寺庙位于距离道路西端 tit_i 米处。

\hspace{15pt}请回答以下 qq 个问题。

\hspace{15pt}第 ii 个问题(1≦i≦q1 \leqq i \leqq q):如果从距离道路西端 xix_i 米的地点出发,并可以在道路上自由移动,访问一座神社和一座寺庙所需的最小移动距离是多少米?(途中可以经过多于一座神社或寺庙也没有关系。)

输入格式

\hspace{15pt}第一行输入三个整数 $a, b, q \left(1 \leqq a, b \leqq 10^5;\ 1 \leqq q \leqq 10^5\right)$ 代表神社数量、寺庙数量和问题数量。

\hspace{15pt}第二行输入 aa 个整数 $s_1, s_2, \dots, s_a \left(1 \leqq s_1 < s_2 < \dots < s_a \leqq 10^{10}\right)$ 代表每家神社到道路西端的距离。

\hspace{15pt}第三行输入 bb 个整数 $t_1, t_2, \dots, t_b \left(1 \leqq t_1 < t_2 < \dots < t_b \leqq 10^{10}\right)$ 代表每座寺庙到道路西端的距离。

\hspace{15pt}第四行输入 qq 个整数 $x_1, x_2, \dots, x_q \left(1 \leqq x_i \leqq 10^{10}\right)$ 代表每个问题的出发地点到道路西端的距离。

\hspace{15pt}保证 $s_1, s_2, \dots, s_a, t_1, t_2, \dots, t_b, x_1, x_2, \dots, x_q$ 两两互不相同。

\hspace{15pt}输入中的所有整数之间只用空白字符(空格或换行)分隔,行数不固定,按顺序读取这些整数即可。

输出格式

\hspace{15pt}输出 qq 行,第 ii 行输出一个整数,代表第 ii 个问题的答案。

测试样例

2 3 4
100 600
400 900 1000
150 2000 899 799
350
1400
301
399

样例 1 解释

\hspace{15pt}有 22 家神社和 33 座寺庙,神社分别位于距离西端 100, 600100,\ 600 米处,寺庙分别位于 400, 900, 1000400,\ 900,\ 1000 米处。

∙ \hspace{23pt}\bullet\,问题 11:从距离西端 150150 米处出发,最优方案是先向西走 5050 米到神社,再向东走 300300 米到寺庙;

∙ \hspace{23pt}\bullet\,问题 22:从距离西端 20002000 米处出发,最优方案是先向西走 10001000 米到寺庙,再向西走 400400 米到神社。途中会经过一座寺庙,但没有关系;

∙ \hspace{23pt}\bullet\,问题 33:从距离西端 899899 米处出发,最优方案是先向东走 11 米到寺庙,再向西走 300300 米到神社;

∙ \hspace{23pt}\bullet\,问题 44:从距离西端 799799 米处出发,最优方案是先向西走 199199 米到神社,再向西走 200200 米到寺庙。

1 1 3
1
10000000000
2 9999999999 5000000000
10000000000
10000000000
14999999998

样例 2 解释

\hspace{15pt}道路很长,可能需要移动的距离会超过 3232 位整数的范围。