A higher resolution is required to access the IDE

- 8

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

Let's define**"fibonomial sequence"**as a sequence of polynomials (

**P0(x), P1(x)...Pi(x),...**) such that:

**P2(x) = P1(P0(x)) + P0(P1(x))**

**P3(x) = P2(P1(x)) + P1(P2(x))**

...

**P{n+2}(x) = P{n+1}(Pn(x)) + Pn(P{n+1}(x))**.

Given either the coefficients or the roots of the first two polynomials

`P0`and

`P1`, output the fibonomials sequence of size

`n`for a given integer

`x`(i.e.

**P0(x), P1(x), P2(x), ..., P{n-1}(x)**).

If an element of the sequence is quite big, i.e. abs(Pi(x)) >= 10^12, format it in scientific notation with 6 decimal precision (7 significant figures, Cf. example 2 below).

The string entry

`defined_by`takes one of the values

`a0`+

`a1`x +

`a2`x^2 + ... +

`ai`x^i + ...

and likewise P1 =

`b0`+

`b1`x +

`b2`x^2 + ... +

`bi`x^i + ...

`a0`) (x-

`a1`) (x-

`a2`) ... (x-

`ai`) ...

and likewise P1 = (x-

`b0`) (x-

`b1`) (x-

`b2`) ... (x-

`bi`) ...

**Example 1:**

`defined_by`=

`ai`=

**-1 2**==> P0 =

**2x-1**...(eq. 1)

`bi`=

**3 0 -1**==> P1 =

**-x^2+3**...(eq. 2)

`x`=

**-5**

`n`=

**3**

Solution:

(eq. 1 & 2) ==> P1(P0(x)) = -P0^2+3= -(2x-1)^2+3 ... (eq. 3)

(eq. 1 & 2) ==> P0(P1(x)) = 2*P1-1 = 2*(-x^2+3)-1 ... (eq. 4)

(eq. 3 & 4) ==> P2(x) = P1(P0(x))+P0(P1(x)) = -(2*x-1)^2+3 + 2*(-x^2+3)-1 ... (eq. 5)

Thus, for x = -5:

(eq. 1) ==> P0(-5) = 2*(-5)-1 =

**-11**

(eq. 2) ==> P1(-5) = -(-5)^2+3 =

**-22**

(eq. 5) ==> P2(-5) = -(2*(-5)-1)^2+3+2*(-(-5)^2+3)-1 =

**-163**

**Example 2:**

`defined_by`=

`ai`=

**0 0 0 1 -1**==> P0 =

**x^3 (x-1) (x+1)**=

**x^5 - x^3**...(eq. 1)

`bi`=

**1000**==> P1 =

**x-1000**...(eq. 2)

`x`=

**-10**

`n`=

**3**

Solution:

(eq. 1 & 2) ==> P1(P0(x)) = P0 - 1000 = x^5 - x^3 - 1000 ... (eq. 3)

(eq. 1 & 2) ==> P0(P1(x)) = P1^5 - P1^3 = (x-1000)^5 - (x-1000)^3 ... (eq. 4)

(eq. 3 & 4) ==> P2(x) = x^5 - x^3 - 1000 + (x-1000)^5 - (x-1000)^3 ... (eq. 5)

Thus, for x = -10:

(eq. 1) ==> P0(-10) = -10^5 - (-10)^3 =

**-99000**

(eq. 2) ==> P1(-10) = -10 - 1000 =

**-1010**

(eq. 5) ==> P2(-10) = -10^5 - (-10)^3 - 1000 + (-1010)^5 - (-1010)^3 = -1051009019899000 =

**-1.051009E+15**

Input

**Line 1:**The string

`defined_by`

**Line 2:**Integers

`ai`for all the coefficients or roots of the first polynomial

`P0`, separated by a whitespace.

**Line 3:**Integers

`bi`for all the coefficients or roots of the second polynomial

`P1`, separated by a whitespace.

**Line 4:**An integer

`x`for which the fibonomials are evaluated.

**Line 5:**An integer

`n`for the size of the sequence.

Output

**The**

`n`lines:`n`integers elements of the

**fibonomial sequence**, one per line. Output an element in scientific notation

Constraints

1 <=

-2^63 <=

`n`< 32-2^63 <=

`x`< 2^63Example

Input

COEFS -1 2 3 0 -1 -5 3

Output

-11 -22 -163

A higher resolution is required to access the IDE