Hôm nay lớp Chuyên Tin học vinh dự được cả hai thầy Hiếu và thầy Tùng đến giảng bài, giờ ra chơi thầy Hiếu và thầy Tùng tổ chức trò chơi cho lớp như sau: Thầy Hiếu sẽ ghi ra hai dãy số ~x_{1}, x_{2}, x_{3}, ..., x_m~ và dãy ~y_{1}, y_{2}, y_{3}, ..., y_n~; thầy Tùng sẽ ghi ra một dãy số ~s_1, s_2, s_3, ...., s_k~. Bây giờ, với mỗi ~s_z~ thầy Tùng yêu cầu lớp sẽ chọn một số bất kì thuộc dãy ~x_{1}, x_{2}, x_{3}, ..., x_m~ và một số bất kì thuộc dãy ~y_{1}, y_{2}, y_{3}, ..., y_{n}~ sao cho tổng hai số được chọn chênh lệch với ~s_z~ là nhỏ nhất.

Yêu cầu

Là một lập trình viên tương lai, em hãy cùng các bạn lớp Chuyên Tin học giải quyết vấn đề này.

Dữ liệu đầu vào

Gồm bốn dòng:

• Dòng 1: Ghi ba số nguyên dương ~m,\ n,\ k~ ~(1 \le m, n \le 10^5;\ k \le 500)~;
• Dòng 2: Ghi ~m~ số nguyên ~x_{1}, x_{2}, x_{3}, ..., x_m~ ~(|x_i| \le 10^9)~, ~(i = 1, 2, 3, ..., m)~.
• Dòng 3: Ghi ~n~ số nguyên ~y_{1}, y_{2}, y_{3}, ..., y_n~ ~(|y_j| \le 10^9)~, ~(j = 1, 2, 3, ..., n)~.
• Dòng 4: Ghi ~k~ số nguyên ~s_1, s_2, s_3, ..., s_k~ ~(|s_z| \le 10^9)~, ~(z = 1, 2, 3, ..., k)~.

Dữ liệu đầu ra

Gồm một dòng duy nhất chứa ~k~ số nguyên là giá trị chênh lệch nhỏ nhất của từng sẽ với tổng hai số được chọn ở dãy ~x~ và dãy ~y~, các số cách nhau một dấu cách.

Ràng buộc dữ liệu

• Có 40% số điểm ứng với các test có ~m, n \le 1000,\ k \le 10~;
• Có 30% số điểm ứng với các test có ~m, n \le 100000,\ k \le 10~;
• Có 30% số điểm ứng với các test có ~m, n \le 100000,\ k \le 500~.

Ví dụ

Ví dụ 1

INPUT

3 4 2
1 3 2
-1 5 3 2
2 9

OUTPUT

0 1

Giải thích:

• Với ~s_1 = 2~, ta chọn tại dãy ~x~ giá trị bằng ~1~; dãy ~y~ giá trị bằng ~1~, từ đó độ chênh lệch bằng ~0~.
• Với ~s_2 = 9~, ta chọn tại dãy ~x~ giá trị bằng ~3~; dãy ~y~ giá trị bằng ~5~. Với tổng bằng ~8~, ta có độ chênh lệch bằng ~1~.