Đồng bằng JOI là một đồng bằng rất rộng trải dài từ tây sang đông. Có thể xem đồng bằng này là một trục số, với chiều dương hướng về phía đông. Mùa đông đã đến và trên đồng bằng có \(N\) quả cầu tuyết ở các tọa độ khác nhau. Các quả cầu được đánh số từ \(1\) đến \(N\) theo thứ tự từ tây sang đông. Ban đầu, quả cầu thứ \(i\) (\(1 \le i \le N\)) nằm tại tọa độ nguyên \(X_i\).

Vào mùa đông, gió trên đồng bằng JOI thổi rất mạnh. Bạn có dữ liệu quan sát gió trong \(Q\) ngày. Gió của ngày thứ \(j\) (\(1 \le j \le Q\)) được biểu diễn bởi số nguyên \(W_j\). Nếu \(W_j\) âm, gió thổi về phía tây; nếu \(W_j\) không âm, gió thổi về phía đông. Độ mạnh của gió là \(|W_j|\).

Khi gió thổi, mỗi quả cầu tuyết lăn cùng hướng với gió một quãng đường bằng độ mạnh của gió. Nói cách khác, nếu đầu ngày thứ \(j\) một quả cầu ở tọa độ \(x\), nó sẽ lăn từ \(x\) đến \(x+W_j\) và kết thúc ngày tại \(x+W_j\). Trong mỗi ngày, tất cả các quả cầu lăn đồng thời và cùng tốc độ.

Ban đầu, toàn bộ đồng bằng được phủ tuyết. Khi một quả cầu lăn qua một đoạn còn tuyết, tuyết bám vào quả cầu làm tăng khối lượng của nó, và tuyết trên đoạn đó biến mất. Cụ thể, với một số nguyên \(a\), nếu đoạn từ \(a\) đến \(a+1\) còn tuyết, khi một quả cầu lăn qua đoạn này, khối lượng của nó tăng \(1\) và tuyết trên đoạn đó biến mất. Nếu quả cầu lăn qua đoạn không còn tuyết, khối lượng của nó không đổi.

Ban đầu, khối lượng của mọi quả cầu đều bằng \(0\). Trong \(Q\) ngày quan sát không có tuyết mới rơi.

Cho tọa độ ban đầu của các quả cầu và dữ liệu gió trong \(Q\) ngày, hãy tính khối lượng của từng quả cầu vào cuối ngày thứ \(Q\).

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N Q
X_1 X_2 ... X_N
W_1
...
W_Q

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) chứa khối lượng của quả cầu thứ \(i\) vào cuối ngày thứ \(Q\).

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le Q \le 200\,000\).
• \(|X_i| \le 10^{12}\) với mọi \(1 \le i \le N\).
• \(X_i < X_{i+1}\) với mọi \(1 \le i < N\).
• \(|W_j| \le 10^{12}\) với mọi \(1 \le j \le Q\).

Phân nhóm

• Nhóm 1 (33 điểm): \(N \le 2000\), \(Q \le 2000\).
• Nhóm 2 (67 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 3
-2 3 5 8
2
-4
7

5
4
2
6

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

3000000000000

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

14
8
7
9
11
10
9
8
5
10

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.