题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，以及一个长度为 $m(m \le n)$ 的数列 $b_1, b_2, \ldots, b_m$。

你需要对数列 $a$ 进行 $n-m+1$ 轮操作：第 $i$ 轮操作，你需要选择从 $a_i$ 开始的连续 $m$ 个数，并将每个元素加上数列 $b$ 上对应元素的数值。

更具体一点地说：

• 第 $1$ 轮：你需要将 $a_1$ 加上 $b_1$（$a_1 \leftarrow a_1 + b_1$），将 $a_2$ 加上 $b_2$（$a_2 \leftarrow a_2 + b_2$），……，将 $a_m$ 加上 $b_m$（$a_m \leftarrow a_m + b_m$）
• 第 $2$ 轮：你需要将 $a_2$ 加上 $b_1$（$a_2 \leftarrow a_2 + b_1$），将 $a_3$ 加上 $b_2$（$a_3 \leftarrow a_3 + b_2$），……，将 $a_{m+1}$ 加上 $b_m$（$a_{m+1} \leftarrow a_{m+1} + b_m$）
• 第 $3$ 轮：你需要将 $a_3$ 加上 $b_1$（$a_3 \leftarrow a_3 + b_1$），将 $a_4$ 加上 $b_2$（$a_4 \leftarrow a_4 + b_2$），……，将 $a_{m+2}$ 加上 $b_m$（$a_{m+2} \leftarrow a_{m+2} + b_m$）
• ……
• 第 $n+m-1$ 轮：你需要将 $a_{n-m+1}$ 加上 $b_1$（$a_{n-m+1} \leftarrow a_1 + b_1$），将 $a_{n-m+2}$ 加上 $b_2$（$a_{n-m+2} \leftarrow a_2 + b_2$），……，将 $a_n$ 加上 $b_m$（$a_n \leftarrow a_m + b_m$）

输出进行完上述 $n-m+1$ 轮操作之后的数列 $a$。

输入格式

第一行，两个整数 $n$ 和 $m$（$1 \le m \le n \le 2 \cdot 10^5$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$。

第三行，$m$ 个整数 $b_1, b_2, \ldots, b_m(1 \le b_i \le 10^9)$。

输出格式

输出共一行，包含 $n$ 个整数，两两之间以一个空格分隔，表示执行完上述 $n-m+1$ 轮操作之后的数列 $a$。

6 2
1 1 1 1 1 1
1 1

2 3 3 3 3 2

8 5
1 2 3 4 5 6 7 8
1 2 3 4 5

2 5 9 14 19 18 16 13

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$m \le n \le 20; a_i, b_i \le 10^3$
• 对于 $60\%$ 的数据，$m \le n \le 2000; a_i, b_i \le 10^6$
• 对于 $100\%$ 的数据，$1 \le m \le n \le 2 \cdot 10^5; 1 \le a_i, b_i \le 10^9$