## An FFT Problem VI

View as PDF

Points: 30
Time limit: 10.0s
Java 15.0s
PyPy 2 30.0s
PyPy 3 30.0s
Memory limit: 256M

Author:
Problem type

#### Statement

Alice and Bob have huge dice where the possible roll values are from to (inclusive).

These huge dice have many many faces. In particular, Alice's die has faces with roll value , while Bob's die has faces with roll value .

Alice and Bob roll their dice at the same time. Their score is the sum of their roll values. Alice and Bob are wondering: for each of the possible scores from to (inclusive), how many different ways could they have have rolled the score ?

Two ways are considered different if Alice rolls a different face or Bob rolls a different face, regardless of their value.

#### Input Specification

The first line of input will contain .

The second line of input will contain space-separated integers, .

The third line of input will contain space-separated integers, .

#### Output Specification

One line containing space-separated integers, the number of ways that a score of can be rolled.

#### Sample Input 1

3
1 2 3 4
5 6 7 8

#### Sample Output 1

5 16 34 60 61 52 32

#### Explanation for Sample 1

The fifth number in the output, , represents the number of ways to get a score of .

There are cases of this happening:

1. Alice rolls a and Bob rolls a . Alice has faces with value and Bob has faces with value . There are ways to roll a in this case.

2. Alice rolls a and Bob rolls a . Alice has faces with value and Bob has faces with value . There are ways to roll a in this case.

3. Alice rolls a and Bob rolls a . Alice has faces with value and Bob has faces with value . There are ways to roll a in this case.

The total of these cases is .

#### Sample Input 2

15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#### Sample Output 2

17 52 106 180 275 392 532 696 885 1100 1342 1612 1911 2240 2600 2992 3095 3164 3198 3196 3157 3080 2964 2808 2611 2372 2090 1764 1393 976 512