Vào tháng 12 cuối Đông, con đường nhỏ sau nhà ngoại Tô Bằng thường ngập trong tuyết, lúc nhỏ cậu bé hay ra sân sau nghịch tuyết. Dịp nghỉ Đông này bố mẹ dẫn Bằng về quê chơi. Vì lớn rồi nên Bằng trở nên đam mê với tính toán những con số hơn vùi đầu trong tuyết. Sau khi theo dõi dự báo thời tiết, Bằng biết được vào ngày hôm nay trời sẽ không có thêm tuyết rơi, thay vào đó là những trận gió lớn theo từng thời điểm khác nhau trong ngày. Do đó cậu tự đặt ra một bài toán hóc búa để bản thân phân tích.

Phía sau nhà được phủ một lớp tuyết kéo dài từ đầu đến cuối con đường, Bằng quyết định đánh tọa độ của các vị trí trên con đường, lấy nhà cậu ấy là gốc tọa độ (điểm \(0\)), các điểm nằm phía trái sẽ có tọa độ âm, phía phải có tọa độ dương. Trên con đường có \(N\) quả cầu tuyết nhỏ (coi như trọng lượng bằng \(0\)) lần lượt nằm tại các tọa độ \(x_1,\ x_2,\ldots,\ x_N\) (\(x_i\) là các số nguyên) được đánh số theo thứ tự từ trái sang phải. Có \(T\) thời điểm trời sẽ nổi gió trong ngày, vào thời điểm thứ \(i\) sẽ có một cơn gió có sức gió \(|s_i|\) thổi qua, nếu \(s_i>0\) thì gió sẽ thổi theo hướng từ trái sang phải, nếu \(s_i<0\) thì gió sẽ thổi theo hướng từ phải sang trái.

Mỗi lần gió thổi, tất cả quả cầu tuyết sẽ lăn theo hướng của gió một quãng đường đúng bằng sức của cơn gió đó. Ví dụ một quả cầu nằm ở tọa độ \(x\), thì vào thời điểm ngọn gió thứ \(j\) thổi, nó sẽ lăn sang tọa độ \(x+s_j\). Nhắc lại, tất cả các quả cầu đều sẽ lăn cùng lúc khi gió thổi, với cùng tốc độ và khoảng cách lăn.

Khi một quả cầu tuyết bất kỳ lăn ngang qua một đoạn đường đang còn được phủ bởi tuyết nó sẽ tích lũy toàn bộ lượng tuyết trên đó và làm tăng kích thước cùng trọng lượng của bản thân (nghĩa là toàn bộ lượng tuyết trên đoạn đường đó sẽ biến mất). Ví dụ, giả sử đoạn đường từ tọa độ \(x\) đến tọa độ \(x+1\) vẫn còn được bao phủ bởi tuyết, nếu một quả cầu bất kỳ lăn qua đoạn đường trên, trọng lượng của nó sẽ tăng thêm \(1\) đơn vị, và tuyết trên đoạn đó sẽ biến mất. Tức là mỗi một lượt lăn, tổng trọng lượng của mỗi quả cầu sẽ tăng lên đúng bằng tổng độ dài của các đoạn đường còn tuyết mà nó lăn qua. Nếu cầu tuyết lăn qua đoạn đường không còn tuyết thì trọng lượng sẽ được giữ nguyên. Nhắc lại, ban đầu các quả cầu có trọng lượng bằng \(0\).

Bằng muốn tính toán xem khối lượng của từng quả cầu tuyết theo thứ tự từ trái sang phải sau \(T\) thời điểm gió thổi là bao nhiêu. Nhưng vì dữ liệu quá lớn nên Bằng không biết kết quả mình tính có chính xác không. Các bạn IT NBK hãy giúp cậu ấy lập trình tính toán để kiểm tra kết quả nhé!

Input

• Dòng đầu chứa hay số nguyên dương \(N,\ T\), lần lượt là số lượng cầu tuyết và số thời điểm gió thổi trong ngày;
• Dòng thứ hai chứa \(N\) số nguyên \(x_1,\ x_2,\ldots,\ x_N\) thể hiện tọa độ ban đầu của các quả cầu tuyết;
• Tiếp theo là \(T\) dòng, dòng thứ \(i\) chứa một số nguyên \(s_i\) thể hiện cơn gió thứ \(i\) trong ngày.

Output

• In ra \(N\) dòng, dòng thứ \(i\) chứa trọng lượng của quả cầu thứ \(i\) sau \(T\) thời điểm gió thổi.

Ràng buộc

• \(1\leq N,\ T\leq2\times10^5\);
• \(|x_i|\leq10^{12}\), \(x_i\leq x_{i+1}\);
• \(|s_i|\leq10^{12}\).

Subtasks

• 40% số điểm có \(N,\ T\leq2000\);
• 60% số điểm còn lại không có ràng buộc gì thêm.

Ví dụ

Sample input 1

4 3
-2 3 5 8
2
-4
7

Sample output 1

5
4
2
6

Note

• Ban đầu các quả cầu lần lượt nằm ở các tọa độ \(-2,\ 3,\ 5,\ 8\), với trọng lượng tất cả đều bằng \(0\);
• Lần đầu gió thổi với sức gió là \(2\) theo chiều từ trái sang phải, tọa độ các quả cầu lúc này lần lượt là \(0,\ 5,\ 7,\ 10\), với trọng lượng lần lượt là \(2,\ 2,\ 2,\ 2\);
• Lần thứ hai gió thổi với sức gió là \(4\) theo chiều từ phải sang trái, tọa độ các quả cầu lúc này lần lượt là \(-4,\ 1,\ 3,\ 6\), với trọng lượng lần lượt là \(4,\ 4,\ 2,\ 3\);
• Lần cuối cùng gió thổi với sức gió là \(7\) theo chiều từ trái sang phải, tọa độ các quả cầu lúc này lần lượt là \(3,\ 8,\ 10,\ 13\), với trọng lượng lần lượt là \(5,\ 2,\ 4,\ 6\);

Sample input 2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

Sample output 2

3000000000000

Sample input 3

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6

Sample output 3

14
8
7
9
11
10
9
8
5
10