Trạm dừng chân

Trên một tuyến đường dài có \(m\) xe khách đang lưu thông và \(n\) trạm dừng chân được xây dựng dọc theo tuyến đường. Tuyến đường này được biểu diễn trên một trục số, mỗi đơn vị trên trục số tương ứng với \(1\) km. Hiện tại:

• Xe thứ \(i\) (\(1 \le i \le m\)) đang ở vị trí \(a_i\).
• Trạm dừng chân thứ \(j\) (\(1 \le j \le n\)) nằm ở vị trí \(b_j\).

Khi cần nghỉ ngơi hoặc tiếp nhiên liệu, mỗi xe luôn tìm trạm dừng chân gần nhất để tối ưu quá trình di chuyển.

Yêu cầu: Hãy xác định quãng đường mà mỗi xe cần di chuyển để đến trạm dừng chân gần nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(m\) và \(n\).
• Dòng thứ hai chứa \(m\) số nguyên dương \(a_1, a_2, \dots, a_m\), mỗi số có giá trị không vượt quá \(10^6\).
• Dòng thứ ba chứa \(n\) số nguyên dương \(b_1, b_2, \dots, b_n\), mỗi số có giá trị không vượt quá \(10^6\).

Output

• Ghi ra một dòng gồm \(m\) số nguyên, số thứ \(i\) cho biết quãng đường xe thứ \(i\) di chuyển đến trạm dừng chân gần nhất tìm được.

Example

5 4
12 25 40 50 70
10 30 50 80

2 5 10 0 10

Scoring

• \(70\%\) số điểm tương ứng với các test có \(m, n \le 10^3\).
• \(30\%\) số điểm tương ứng với các test có \(m, n \le 10^5\).