Dãy số

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 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. Giả sử tổng hai số tìm được là \(t\) thì chênh lệch là: \(|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 mỗ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ữ liệu vào:

• 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.

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\).

Output

In ra \(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

Input:

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

Output:

0
1

Note

Với \(s = 2\): chọn \(1 + 1 = 2\), chênh lệch \(0\). Với \(s = 9\): tổng lớn nhất là \(3 + 5 = 8\), chênh lệch \(1\).