H. Counting Sort?
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
I want to end this life impulsively for the decisive time instead of living on the rails that have been laid out for me.
Kashii Moimi & Kaai Yuki, The Decisive Hour

For an array $$$[b_1, b_2, \ldots, b_m]$$$ where $$$0 \le b_i \le m$$$, define $$$f(b)$$$ as an array $$$[c_1, c_2, \ldots, c_m]$$$ such that $$$c_i$$$ is the number of occurrences of $$$i$$$ in the array $$$b$$$.

Define the value $$$g(b)$$$ of an array $$$[b_1, b_2, \ldots, b_m]$$$, where $$$0 \le b_i \le m$$$, as follows:

  • Initially, there is an empty set $$$S$$$. Create an array $$$d$$$ that is initially equal to $$$b$$$.
  • Then, you perform the following operation $$$100^{100}$$$ times: Insert $$$d$$$ into $$$S$$$, then set $$$d \gets f(d)$$$.
  • $$$g(b)$$$ is the number of distinct arrays in $$$S$$$ after the operations.

Now you are given two integers $$$n$$$ and $$$k$$$, as well as an array $$$[r_1, r_2, \ldots, r_n]$$$. For every $$$1\le p\le k$$$, count the number of arrays $$$[a_1, a_2, \ldots, a_n]$$$ where $$$0 \le a_i \le r_i$$$ such that $$$g(a) = p$$$. Since this number may be large, output it modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le k \le 1000$$$).

The second line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i \le n$$$).

It is guaranteed that the sum of $$$n^3$$$ over all test cases does not exceed $$$50^3$$$.

Output

For each test case, output $$$k$$$ integers — the number of arrays $$$[a_1, a_2, \ldots, a_n]$$$ with $$$0 \le a_i \le r_i$$$ such that $$$g(a) = 1, 2, \ldots, k$$$, respectively.

Print the answer modulo $$$998\,244\,353$$$.

Example
Input
6
2 5
2 2
5 6
4 5 1 4 5
7 7
7 6 5 5 6 7 6
11 7
5 8 9 10 11 4 10 11 7 8 11
12 7
12 12 12 12 12 12 12 12 12 12 12 12
5 10
0 0 0 0 1
Output
2 1 2 2 2 
2 4 14 60 554 395 
2 6 35 627 63856 171611 490235 
2 10 83 10495 286935908 71004446 630281080 
2 11 132 48996 207819517 474452948 13828302 
1 1 0 0 0 0 0 0 0 0
Note

In the first test case, $$$g([0, 0]) = g([1, 0]) = 1$$$, $$$g([0, 1]) = 2$$$, $$$g([2, 0]) = g([0, 2]) = 3$$$, $$$g([1, 1]) = g([2, 2]) = 4$$$, and $$$g([1, 2]) = g([2, 1]) = 5$$$.

In the second test case, $$$f([4, 5, 1, 4, 5]) = [1, 0, 0, 2, 2]$$$, $$$f([1, 0, 0, 2, 2]) = [1, 2, 0, 0, 0]$$$, $$$f([1, 2, 0, 0, 0]) = [1, 1, 0, 0, 0]$$$, $$$f([1, 1, 0, 0, 0]) = [2, 0, 0, 0, 0]$$$, $$$f([2, 0, 0, 0, 0]) = [0, 1, 0, 0, 0]$$$, $$$f([0, 1, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$, $$$f([1, 0, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$. So, $$$g([4, 5, 1, 4, 5]) = 7$$$.