Cộng dãy

Sau khi giao hai bài toán về số học và hình học, buổi học tiếp theo Giáo sư \(X\) lại "hành" lũ học trò của mình bằng một bài toán xử lý dãy số như sau:

Cho một dãy số nguyên \(A\) có \(n\) phần tử \(a_1, a_2, \dots, a_n\). Giáo sư lần lượt thực hiện \(q\) phép biến đổi. Ở mỗi phép biến đổi, ông lấy một số nguyên \(x\) rồi cộng vào tất cả các phần tử của dãy lên một lượng \(x\).

Yêu cầu. Sau mỗi phép biến đổi, hãy tính tổng giá trị tuyệt đối của tất cả các phần tử trong dãy, tức là giá trị

Input

• Dòng đầu tiên chứa hai số nguyên \(n, q\) (\(1 \le n, q \le 5 \cdot 10^5\)) — số phần tử của dãy và số phép biến đổi.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^7\)) — dãy ban đầu.
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x\) (\(|x| \le 10^7\)) — giá trị được cộng vào toàn bộ dãy ở phép biến đổi tương ứng.

Output

Ghi ra gồm \(q\) dòng, mỗi dòng là một số nguyên duy nhất — tổng giá trị tuyệt đối của các phần tử trong dãy sau phép biến đổi tương ứng.

Input

%
5 3
-1 3 -2 4 0
3
-4
1

Output

%
19
11
10

Input

%
6 5
-1 -2 3 -3 2 1
5
1
-6
-8
-2

Output

%
30
36
12
48
60

Scoring

• (50%) \(n, q \le 5000\).
• (50%) Không có điều kiện gì thêm.