Hai bạn An và Bình chơi trò chơi trên hai dãy số như sau: An sẽ tạo ra hai dãy số nguyên \(x_1, x_2, \ldots, x_m\) và \(y_1, y_2, \ldots, y_n\). Sau đó, Bình sẽ chọn một số nguyên \(s\) và yêu cầu An chọn 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. Giả sử tổng của hai số tìm được là \(t\) thì chênh lệch: \(|t - s|\).

Yêu cầu: Cho hai dãy số nguyên \(x_1, x_2, \ldots, x_m\) và \(y_1, y_2, \ldots, y_n\) mà An đã tạo ra, cho \(s_1, s_2, \ldots, s_k\) là \(k\) câu hỏi của Bình. Với câu hỏi \(s_u\) \((1 \le u \le k)\) đưa ra giá trị chênh lệch nhỏ nhất của \(s_u\) với tổng hai số tìm được.

Input

• Dòng đầu chứa ba số nguyên dương \(m, n, k\) (\(m, n \le 10^5, k \le 500\)).
• Dòng thứ hai chứa \(m\) số nguyên \(x_1, x_2, \ldots, x_m\) (\(|x_i| \le 10^9, 1 \le i \le m\)).
• Dòng thứ ba chứa \(n\) số nguyên \(y_1, y_2, \ldots, y_n\) (\(|y_j| \le 10^9, 1 \le j \le n\)).
• Dòng thứ tư chứa \(k\) số nguyên \(s_1, s_2, \ldots, s_k\) (\(|s_u| \le 10^9, 1 \le u \le k\)).

Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi dấu cách.

Output

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

Example

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

0
1

Ràng buộc

• 40% số điểm của bài ứng với các test có \(m, n \le 10^3, k \le 10\).
• 40% số điểm của bài ứng với các test có \(m, n \le 10^5, k \le 10\).
• 20% số điểm của bài ứng với các test có \(m, n \le 10^5, k \le 500\).