Description

ftiasch has $n$ items with volumes $w_1,w_2,\dots,w_n$. Due to her negligence, the $i$-th item is missing.

“How many ways are there to exactly fill a knapsack of capacity $x$ using the remaining $n-1$ items?” — this is a classic problem.

She records the answer as $\text{cnt}(i,x)$ and wants the table of $\text{cnt}(i,x)$ for all $i \in [1,n]$ and $x \in [1,m]$.

Input Format

The first line contains two integers $n,m$, the number of items and the maximum capacity.
The second line contains $n$ integers $w_1,w_2,\dots,w_n$, the volume of each item.

Output Format

Output an $n \times m$ matrix, giving the last digit of $\text{cnt}(i,x)$.

3 2
1 1 2

11
11
21

Hint

Constraints
For $100\%$ of the testdata, $1 \le n,m \le 2000$, and $1 \le w_i \le 2000$.

Sample explanation
If item $3$ is missing, there is exactly one way to fill capacity $2$, namely choosing items $1$ and $2$.

—
$\text{upd 2023.8.11}$: Added five new hack test sets.

Translated by ChatGPT 5