問題文

カナリアは以下のような問題を作った．

Fox the Optimizing Chef

長さ N の整数列 A = (A_1, \ldots, A_N) と B = (B_1, \ldots, B_N) が与えられます．

きつねは，あるレストランを経営しています．今このレストランには，1 から N までの番号のついた N 人の客がいます．客 i は，調理に A_i 単位時間かかる料理を注文し，料理を食べるのに B_i 単位時間かかります．

各整数 k (1 \le k \le N) について，以下の問題を解いてください．

きつねが k 人の客を選び，選ばなかった N - k 人を帰宅させます．そして，k 人のための料理を好きな順で作っていきます．2 個以上の料理を同時に作ることはできません．客は，自分の料理が完成した瞬間に食事を開始します．きつねの労働時間は，「最初の料理を作り始めてから，k 人の客すべてが食事を終えるまでの時間」です．きつねの労働時間の最小値を求めてください．

しかし，この問題はロシアの国内コンテストでほぼ既出であることが発覚した．そこで，カナリアは問題を以下のように変形した．

Fox the Counting Chef

整数 V と，長さ N の整数列 B = (B_1, \ldots, B_N) が与えられます．

長さが N で各要素が 1 以上 V 以下の整数列 A = (A_1, \ldots, A_N) は V^N 通り存在しますが，それぞれの A に対し (与えられた B とともに) 問題 "Fox the Optimizing Chef" を解き，各整数 k (1 \le k \le N) についてその答えの総和を 998244353 で割った余りを求めてください．

問題 "Fox the Counting Chef" を解け．

制約

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

入力例 1

2 2
1 2

出力例 1

10 16

k = 2 の場合を考える．各 A に対する元の問題の答えは以下のようになる：

• A = (1, 1)：労働時間の最小値は 3．
• A = (1, 2)：労働時間の最小値は 4．
• A = (2, 1)：労働時間の最小値は 4．
• A = (2, 2)：労働時間の最小値は 5．

よって，3 + 4 + 4 + 5 = 16 を出力する．

入力例 2

3 5
1 2 4

出力例 2

448 787 1255

入力例 3

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

出力例 3

663655052 615617049 323725023 554911324 803518888 499232802 916051842 54293837 639852351 260050903