Drawing a picture

Time limit2sMemory limit512 MB

Summary

Colors cycle through cells of a row-major grid; each cell area is H_i times W_j. Report the total area covered by each color.

Level: Medium7 of 10
Topics: Math, Prefix sum, Combinatorics, Implementation
Solved: No attempts yet

Problem

Sangsu paints a picture on a grid with N rows and M columns using L colors. He paints row 1 first, then row 2, and so on through row N. Inside one row he paints column 1 first, then column 2, and so on through column M. He uses color 1, then color 2, up to color L, and after color L he goes back to color 1.

Row i has height $H_i$ and column j has width $W_j$ , so the cell in row i and column j has area $H_i \times W_j$ .

Sangsu does not want to waste paint, so he wants to know how much of each color he needs before he starts. Compute the total area painted with each color.

Input

The first line contains N, M, and L. ( $1 \le N, M, L \le 123456$ )

The second line contains N positive integers $H_1, H_2, \dots, H_N$ , the height of each row, separated by spaces. The sum of $H_i$ does not exceed $10^9$ .

The third line contains M positive integers $W_1, W_2, \dots, W_M$ , the width of each column, separated by spaces. The sum of $W_j$ does not exceed $10^9$ .

Output

Print L lines. Line k contains the total area painted with color k.

Hint

The picture Sangsu paints in the first example looks like this.

Examples2

Example 1
Input
```
4 5 3
2 4 3 4
2 4 1 2 5
```
Expected output
```
63
70
49
```
Example 2
Input
```
1 1 1
1
1
```
Expected output
```
1
```