*Link to blog post:*

*http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-d.html*

**2009 ACM ICPC Asia Manila**

October 22 – 23, 2009

Problem D: ‘Composition of Polynomials’

October 22 – 23, 2009

Input file: d.in

Output file: stdout

Execution time limit: 15 seconds

Given two polynomials, p(x) of degree M, and q(x) of degree N, both with integer coefficients, your problem is to write a computer program that prints the coefficients of the composition polynomial f(x) = p(q(x)).

For example, if p(x) = 2x^3 + 5x – 4 and q(x) = 3x^2 – 4x + 1, then f(x) = p(q(x)) = 2(3x^2 – 4x + 1)^3 + 5( 3x^2 – 4x + 1) – 4 = 54x^6 – 216x^5 + 342x^4 – 272x^3 + 129x^2 – 44x + 3

INPUT. Input shall consist of several data sets. Each data set will be given in three lines of input. The first line will give the values of M and N, separated by one or more spaces. The second line will give the coefficients of each term of p(x), separated by one or more spaces, and arranged in increasing powers of x. The third line will give the coefficients of each term of q(x), separated by one or more spaces, and arranged in increasing powers of x. Both M and N will be between 0 and 10, inclusive. Each coefficient will be small, in the range -20 to 20 inclusive, but a small value raised to 10th power is not guaranteed to be a small integer. Input for the next data set will immediately follow that of the previous data set. An input of M = 0 and N = 0 will signify the end of input data.

**SAMPLE INPUT**

3 2

-4 5 0 2

1 -4 3

2 2

-7 0 2

5 3 2

0 0

**OUTPUT.**

For each data set, print one line of output of the form:“Data set N: <

*composition polynomial*>

where N is the data set number, starting from 1, and <

*composition polynomial*>

**OUTPUT FOR SAMPLE INPUT**

Data set 1: 54x^6–216x^5+342x^4–272x^3+129x^2–44x+3

Data set 2: 8x^4+24x^3+58x^2+60x+43

*(Acknowledgment: This problem was contributed by*

.

**Dr. Pablo Manalastas**, Ateneo de Manila University).