题目描述

从前有个富帅叫做小理，他很喜欢出门旅行，每次出门旅行，他会准备很大一个包裹以及一大堆东西，然后尝试各种方案去塞满它。

然而每次出门前，小理都会有个小小的烦恼。众所周知，富帅是很讨妹子喜欢的，所以小理也是有大把大把的妹子，每次出门都会有一只妹子随行。然而这些妹子总是会非常排斥小理准备的众多东西中的一件（也许是因为这件东西是其它妹子送给小理的），这件东西小理是万万不敢带上的，否则的话……嘿嘿嘿。另外，妹子们嫌小理的包裹太丑了，会自带一个包裹去换掉小理的包裹。

小理是个控制欲很强的人，然而这样一来，小理就不知道可以用多少种方案去填充包裹了，所以小理很郁闷。

于是小理找到了聪明的你，希望你能帮助他解决这些问题。

另外，小理是个典型的懒人，他不希望每次带不同的妹子出去都麻烦你，所以他希望你能给出有 $K_1..K_n$ 件物品，第 $i$ 件不能带并且包裹大小为 $1..M$ 的所有方案数。

输入格式

输入共两行。

第一行，两个整数 $n,m$，分别表示物品数量和妹子带的包裹的最大容积。

第二行，$n$ 个正整数，分别表示物品 $K_i$ 的体积。

输出格式

输出共 $n$ 行。

输出一个 $n \times m$的矩阵，第 $i$ 行 $j$ 列表示包裹容积为 $j$ ，不能带 $i$ 号物品时，装满包裹的方案总数。

为了美观起见，我们只保留方案数的个位。

样例输入输出

样例输入

3 2
1 1 2

样例输出

11
11
21

数据范围

对于 $100%$ 的数据，保证 $1 \le n,m \le 2300,K_i \le 1000$。