题目描述

有 $n$ 个物品，第 $i$ 个物品的体积为 $w_i$。每个物品只有一个，可以选择放入背包或不放入。

现在有一个容量为 $x$ 的背包。我们希望用若干物品恰好装满背包（不多不少）。

但是，如果第 $i$ 个物品丢失了，只能用剩下的 $n-1$ 个物品来恰好装满容量为 $x$ 的背包。这样的装法有多少种？记这个数目对 $10$ 取模后的结果为答案。

请你对所有情况计算答案：

• 对每个 $i$（第 $i$ 个物品丢失）
• 对每个 $x$（背包容量从 $1$ 到 $m$）

将答案写成一个表格。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $w_1,w_2,\dots,w_n$，表示每个物品的体积。

输出格式

输出一个 $n$ 行 $m$ 列的表格。

第 $i$ 行第 $x$ 个数表示：第 $i$ 个物品丢失后，用剩下的物品恰好装满容量为 $x$ 的背包的装法数对 $10$ 取模后的个位数字。

每行输出 $m$ 个数字，数字之间不加空格，直接连在一起。

输入输出样例 #1

输入 #1

3 2
1 1 2

输出 #1

11
11
21

说明/提示

【数据范围】
$1\le n,m \le 2000$，$1\le w_i\le 2000$。

所有答案均对 $10$ 取模，即只保留个位数字。

【样例解释】
物品体积分别是 $1,1,2$。样例中所有装法数都不超过 $9$，因此取模后不变。

• 如果第 $3$ 个物品丢失，剩下两个体积都是 $1$ 的物品。
  • 背包容量为 $1$：可以选任意一个，有 $2$ 种装法。
  • 背包容量为 $2$：两个都选，有 $1$ 种装法。
    所以第 $3$ 行输出 21。

第 1 个物品丢失时，剩下体积为 $1$ 和 $2$ 的物品：

• 容量为 $1$：选体积为 $1$ 的物品，有 $1$ 种装法。
• 容量为 $2$：选体积为 $2$ 的物品，有 $1$ 种装法。 所以第 1 行输出 11。

第 2 个物品丢失时，剩下体积为 $1$ 和 $2$ 的物品，同理输出 11。