Trò chơi trên dãy số

Hai bạn $A$ và $B$ chơi trò chơi trên hai dãy số như sau: $A$ sẽ tạo ra hai dãy số nguyên $x_1,x_2,\dots ,x_m$ và $y_1,y_2,\dots ,y_n$. Sau đó, $B$ sẽ chọn một số nguyên $s$ và yêu cầu $A$ tìm một số thuộc dãy thứ nhất và một số thuộc dãy thứ hai sao cho tổng hai số được chọn chênh lệch với $s$ là nhỏ nhất.

Yêu cầu: Cho hai dãy số nguyên $x_1,x_2,\dots ,x_m$ và $y_1,y_2,\dots ,y_n$ mà $A$ tạo ra, cho $s_1,s_2,\dots ,s_k$ là $k$ câu hỏi của $B$. Với mỗi câu hỏi $s_i$ ($i=1,2,\dots ,k$), đưa ra giá trị chênh lệch nhỏ nhất của $s_i$ với tổng hai số tìm được, tức là giá trị nhỏ nhất của $|x_p+y_q-s_i|$ với $1\le p\le m$, $1\le q\le n$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương $m,n,k$;
• Dòng thứ hai chứa $m$ số nguyên $x_1,x_2,\dots ,x_m$ ($|x_i|\le {10}^9$);
• Dòng thứ ba chứa $n$ số nguyên $y_1,y_2,\dots ,y_n$ ($|y_i|\le {10}^9$);
• Dòng thứ tư chứa $k$ số nguyên $s_1,s_2,\dots ,s_k$ ($|s_i|\le {10}^9$).

Dữ liệu ra

Gồm $k$ dòng, dòng thứ $i$ ghi giá trị chênh lệch nhỏ nhất của $s_i$ với tổng hai số tìm được.

Ràng buộc

• $1\le m,n\le {10}^5$; $1\le k\le 500$.
• $|x_i|,|y_i|,|s_i|\le {10}^9$.

Subtasks

• Có $40\%$ số test ứng với $40\%$ số điểm của bài có $m,n\le 1000$; $k\le 10$;
• Có $40\%$ số test khác ứng với $40\%$ số điểm của bài có $m,n\le {10}^5$; $k\le 10$;
• Có $20\%$ số test còn lại với $20\%$ số điểm còn lại của bài có $m,n\le {10}^5$; $k\le 500$.

Ví dụ