题目描述

ftiasch 有 $n$ 个物品，体积分别是 $w_{1\cdots n}$。由于她的疏忽，第 $i$ 个物品丢失了。

“要使用剩下的 $n-1$ 个物品装满容积为 $x$ 的背包，有几种方法呢？”——这是经典的问题了。

她把答案记为 $\text{Count}(i, x)$，想要得到所有 $1 \leq i \leq n$，$1 \leq x \leq m$ 的 $\text{Count}(i, x)$ 表格。

输入格式

第一行两个整数 $n$ 和 $m$，表示物品的数量和最大的容积。

第二行 $n$ 个整数 $w_{1\cdots n}$，表示物品的体积。

输出格式

一个 $n\times m$ 的矩阵，分别表示 $\text{Count}(i, x)$ 末位数字。

3 2
1 1 2

11
11
21

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^3$。