N. Nobita's Homework! Help Me Doraemon
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Nobita has once again forgotten his homework. This time, Ajarn Nat asked him to design a special grid. Luckily, Doraemon pulls out a grid-maker-from-anywhere gadget that instantly creates such a grid.

The rules of the grid-maker-from-anywhere are as follows:

  • Nobita gives Doraemon two sequences $$$a$$$ and $$$b$$$ of equal length $$$n$$$.
  • The first element is always the same, i.e., $$$a_1=b_1$$$.
  • Doraemon's gadget uses these to construct a square grid with $$$n$$$ rows and $$$n$$$ columns.
  • Let $$$f(i,j)$$$ denote the number on the cell at row $$$i$$$ and column $$$j$$$, the value of $$$f(i,j)$$$ is defined as follows:
    • $$$f(1, 1) = a_1 = b_1$$$
    • $$$f(i, 1) = a_i$$$ for all $$$2 \le i \le n$$$.
    • $$$f(1, j) = b_j$$$ for all $$$2 \le j \le n$$$.
    • $$$f(i, j) = f(i-1, j-1)$$$ for all $$$2 \le i,j \le n$$$.

After the grid is built, Ajarn Nat provides Nobita with another sequence $$$x$$$ of length $$$n$$$. For each row $$$i$$$ of the grid, the gadget aligns $$$x$$$ with that row and computes the value $$$ y_i = \sum\limits_{j=1}^{n} f(i,j)\cdot x_j $$$

Collecting all $$$y_i$$$ for all $$$1 \le i \le n$$$ forms a new sequence $$$y$$$ of length $$$n$$$. Nobita must report this sequence $$$y$$$ to finally complete his homework.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \lt 100$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \leq b_i \lt 100$$$).

The fourth line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \leq x_i \lt 100$$$).

It is guaranteed that $$$a_1 = b_1$$$.

Output

A single line consists of $$$n$$$ integers — the sequence $$$y$$$.

Example
Input
4
1 3 5 7
1 2 4 8
1 4 1 2
Output
29 17 22 32
Note

From $$$a = [1, 3, 5, 7]$$$ and $$$b = [1, 2, 4, 8]$$$, the gadget constructs the following grid.

$$$1$$$$$$2$$$$$$4$$$$$$8$$$
$$$3$$$$$$1$$$$$$2$$$$$$4$$$
$$$5$$$$$$3$$$$$$1$$$$$$2$$$
$$$7$$$$$$5$$$$$$3$$$$$$1$$$

The sequence is $$$x=[1,4,1,2]$$$.

  • The gadget aligns $$$x$$$ with the first row, $$$y_1 = 1 \cdot 1 + 2 \cdot4 + 4 \cdot 1 + 8 \cdot 2 = 29$$$.
  • The gadget aligns $$$x$$$ with the second row, $$$y_2 = 3 \cdot 1 + 1 \cdot 4 + 2 \cdot 1 + 4 \cdot 2 = 17$$$.
  • The gadget aligns $$$x$$$ with the third row, $$$y_3 = 5 \cdot 1 + 3 \cdot 4 + 1 \cdot 1 + 2 \cdot 2 = 22$$$.
  • The gadget aligns $$$x$$$ with the fourth row, $$$y_4 = 7 \cdot 1 + 5 \cdot 4 + 3 \cdot 1 + 1 \cdot 2 = 32$$$.