该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

少装一个

小码哥有 $n$ 个物品，体积分别是 $w_1,w_2,\dots,w_n$。由于他的疏忽，第 $i$ 个物品丢失了。要使用剩下的 $n-1$ 个物品装满容积为 $x$ 的背包，有几种方法呢？ 他把答案记为 $\text{ans}(i,x)$，想要得到所有 $i\in[1,n],x\in[1,m]$ 的 $\text{ans}(i,x)$ 表格。

格式

输入格式：

• 第一行两个整数 $n,m$，表示物品的数量和最大的容积；
• 第二行 $n$ 个整数 $w_1,w_2,\dots,w_n$，表示每个物品的体积。

输出格式：

• 输出一个 $n\times m$ 的矩阵，表示 $\text{ans}(i,x)$ 的末位数字。

样例1

输入：

3 2
1 1 2

输出：

11
11
21

备注

• 对于 30% 的数据，$1 \le n,m \le 100,1 \le w_i \le 100$；
• 对于 100% 的数据，$1 \le n,m \le 2000,1 \le w_i \le 2000$；

样例解释：如果物品 3 丢失的话，只有一种方法装满容量是 2 的背包，即选择物品 1 和物品 2。