ftiasch 有 $N$ 个物品，体积分别是 $W_1, W_2, \dots, W_N$。由于疏忽，第 $i$ 个物品丢失了。用剩下的 $N-1$ 个物品装满容积为 $x$ 的背包的方案数记为 $Count(i, x)$，请求出所有满足 $1 \le i \le N, 1 \le x \le M$ 的 $Count(i, x)$ 表格。

输入描述

• 第1行：两个整数 $N(1 \le N \le 2 \times 10^3)$ 和 $M(1 \le M \le 10^3)$，分别表示物品数量和背包最大容积。
• 第2行：$N$ 个整数 $w_1, w_2, \dots, w_N$，表示每个物品的体积。

输出描述

输出一个 $N \times M$ 的矩阵，每个元素为对应 $Count(i, x)$ 的末位数字，每行对应一个物品丢失的情况，按物品顺序排列。

输入样例

3 2
1 1 2

输出样例

11
11
21

提示

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