Problem Description

Kanaria created the following problem:

Fox the Optimizing Chef

You are given two integer sequences of length $ N $: $A\ =\ (A_1,\ \ldots,\ A_N)$ and $B\ =\ (B_1,\ \ldots,\ B_N)$.

The fox runs a restaurant where there are $ N $ customers numbered from $ 1 $ to $ N $. Customer $ i $ orders a dish that takes $ A_i $ units of time to prepare and takes $ B_i $ units of time to eat.

For each integer $ k $ ($1\ \le\ k\ \le\ N$), solve the following problem:

The fox selects $ k $ customers and sends the remaining $N\ -\ k$ customers home. Then, the fox prepares dishes for the $ k $ customers in any order. No more than one dish can be prepared at the same time. Customers start eating their dishes immediately upon completion. The labor time of the fox is defined as the time from when the first dish starts being prepared until all $ k $ customers have finished eating. Find the minimum labor time for the fox.

However, it was discovered that this problem was almost identical to one that appeared in a domestic contest in Russia. Therefore, Kanaria modified the problem as follows:

Fox the Counting Chef

You are given an integer $ V $ and an integer sequence of length $ N $: $B\ =\ (B_1,\ \ldots,\ B_N)$.

There are $ V^N $ possible sequences $A\ =\ (A_1,\ \ldots,\ A_N)$ where each element is an integer between $ 1 $ and $ V $ inclusive. For each of these sequences $ A $ (together with the given $ B $), solve the problem "Fox the Optimizing Chef" and find the sum of the answers for each integer $ k $ ($1\ \le\ k\ \le\ N$) modulo $ 998244353 $.

Solve the problem "Fox the Counting Chef".

Input Format

The input is given from the standard input in the following format:

$ N $ $ V $ $ B_1 $ $ B_2 $ $\cdots$ $ B_N $

Output Format

For each $k\ =\ 1,\ \ldots,\ N$, output the answer in this order, separated by spaces.

Sample Input and Output

Sample Input #1

2 2
1 2

Sample Output #1

10 16

Sample Input #2

3 5
1 2 4

Sample Output #2

448 787 1255

Sample Input #3

10 10
14 38 45 9 19 18 7 18 33 21

Sample Output #3

663655052 615617049 323725023 554911324 803518888 499232802 916051842 54293837 639852351 260050903

Notes/Hints

Constraints

• $1\ \le\ N\ \le\ 30$.
• $1\ \le\ V\ \le\ 20$.
• $1\ \le\ B_i\ \le\ 600$ ($1\ \le\ i\ \le\ N$).

Sample Explanation 1

Consider the case $k\ =\ 2$. The answers for the original problem for each $ A $ are as follows:
- $A\ =\ (1,\ 1)$: The minimum labor time is $ 3 $.
- $A\ =\ (1,\ 2)$: The minimum labor time is $ 4 $.
- $A\ =\ (2,\ 1)$: The minimum labor time is $ 4 $.
- $A\ =\ (2,\ 2)$: The minimum labor time is $ 5 $.
Therefore, output $3\ +\ 4\ +\ 4\ +\ 5\ =\ 16$.

见题面 Input 部分

见题面 Output 部分