Cho hai dãy số nguyên \(a\) và \(b\). Tính các giá trị tại mỗi vị trí khi di chuyển dãy \(b\) từ trái sang phải. Giá trị tại mỗi vị trí là tổng của tích các phần tử chồng nhau của dãy \(a\) và \(b\)

Input

• Dòng đầu tiên bao gồm hai số nguyên \(n\) và \(m\): độ dài của dãy \(a\) và dãy \(b\).
• Dòng tiếp theo gồm \(n\) số nguyên \(a_1, a_2,…,a_n\) là các phần tử của dãy \(a\)
• Dòng tiếp theo gồm \(m\) số nguyên \(b_1, b_2,…,b_n\) là các phần tử của dãy \(b\)

Output

• In ra \(n + m − 1\) số nguyên: giá trị tại mỗi vị trí từ trái sang phải.

Constraints

• \(1\leq n, m \leq 2 ⋅ 10^5\)
• \(1\leq a_i, b_i \leq 100\)

Example

Sample input

5 3  
1 3 2 1 4  
1 2 3

3 11 13 10 16 9 4

Note

• Giải thích:

• Tại vị trí thứ 2, vị trí của mảng \(a\) và \(b\) là:
  

  1 3 2 1 4
  1 2 3
  

• Do đó, giá trị tại vị trí thứ 2 là \(2 ⋅ 1 + 3 ⋅ 3 = 11\)