Polynomial Remainders

Time limit1sMemory limit128 MB

Summary
Compute the remainder polynomial when dividing a given polynomial by x^k + 1, using the fact that x^k ≡ -1.
Level

Medium4 of 10

Topics
Math, Array, Implementation
Solved
No attempts yet

Problem

You are given the polynomial

a(x) = a_n x^n + ... + a_1 x + a_0.

Find the remainder polynomial r(x) when a(x) is divided by x^k + 1.

Input

The input consists of several test cases. The first line of each test case contains two integers n and k. (0 <= n, k <= 10000)

The next line contains n+1 coefficients of a(x), separated by spaces. The coefficients are given in order from a_0 through a_n.

The input ends when n = k = -1.

Output

For each test case, output the coefficients of the remainder polynomial on one line, starting with the constant coefficient r_0.

If the remainder is 0, print only one constant coefficient. Otherwise, if the remainder has degree d, print exactly the d+1 coefficients from r_0 through r_d. Separate adjacent coefficients with a single space.

You may assume every coefficient of the remainder can be represented as a 32-bit integer.

Examples1

  1. Example 1

    Input
    5 2
6 3 3 2 0 1
5 2
0 0 3 2 0 1
4 1
1 4 1 1 1
6 3
2 3 -3 4 1 0 1
1 0
5 1
0 0
7
3 5
1 2 3 4
-1 -1
    Expected output
    3 2
-3 -1
-2
-1 2 -3
0
0
1 2 3 4