Cho mảng ~A~ gồm ~N~ phần tử, mảng ~B~ gồm ~M~ phần tử. Bạn sẽ thực hiện ~N - M + 1~ thao tác, trong đó thao tác thứ ~i~ diễn ra như sau:

Xét các phần tử ~A_i, A_{i+1}, \ldots, A_{i + M - 1}~ và tăng chúng lần lượt lên ~B_1, B_2, \ldots, B_M~ (Hay nói cách khác, ~A_{i + j - 1}~ sẽ được tăng lên ~B_j~).

Bạn cần in ra dãy ~A~ sau khi thực hiện hết các thao tác.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ ~(1 \le M \le N \le 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên dương miêu tả dãy ~A~ ~(A_i \le 10^9)~.
• Dòng thứ ba gồm ~B~ số nguyên dương miêu tả dãy ~B~ ~(B_i \le 10^9)~.

Output:

• In ra dãy ~A~ sau khi thực hiện các thao tác.

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~N,M \le 1000~
• Subtask ~3~ (~30\%~ số điểm): ~B_i = 1~
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

3 2
5 1 3
1 2

Sample Output 1

6 4 5