一群歹徒成功抢劫了城里最著名的拍卖行。现在他们安全地躲在藏身处，存放着偷来的物品。幸运的是，你成功在他们的藏身处放置了一个窃听器。你还拥有每个歹徒的个人档案，其中包含他们声音的录音。你将仔细聆听接下来发生的事情，希望这能帮助你调查这起抢劫案。

每个歹徒恰好偷了一件物品，第 $i$ 个歹徒偷了第 $i$ 件物品。现在，每个歹徒都试图将他的物品放入公共仓库，仓库的总承重为 $K$。仓库是一个小房间，歹徒们一个接一个地存放他们的物品。

当一个歹徒试图将物品放入仓库但放不下时（即仓库中物品的总重量将超过 $K$），他会变得愤怒，并将仓库里的所有物品扔出去。在这样做时，他会告诉其他人：“$j$ 件物品要进垃圾桶了！”，其中 $j$ 是他在尝试存放物品时仓库中已有的物品数量。此时会发生争斗，后续将不再进行存放操作。

由于你在歹徒的仓库里有窃听器，你可以听到歹徒扔出了多少件物品。此外，利用你的个人档案，你可以分辨出每个歹徒的声音。

因此，如果你能预先知道对于所有可能的 $j$ 和 $i$ 值，当第 $i$ 个歹徒扔掉所有 $j$ 件物品时，仓库中可能存在多少种不同的物品子集，这将对你的调查有很大帮助。由于子集数量可能很大，请输出其对 $167772161$ 取模的结果。

输入格式

输入包含两行。第一行包含两个整数 $N$ 和 $K$ ($2 \le N \le 400, 1 \le K \le 400$)，分别表示歹徒的数量和仓库的最大承重。 第二行包含 $N$ 个整数 $w_1, w_2, \dots, w_N$，满足对于每个 $1 \le i \le N$ 都有 $1 \le w_i \le K$。其中 $w_i$ 是第 $i$ 个歹徒偷走的物品重量。

输出格式

输出包含 $N$ 行，每行包含恰好 $N - 1$ 个整数。第 $i$ 行的第 $j$ 个值表示满足以下条件的物品子集数量：子集恰好包含 $j$ 件物品，这些物品可以放入仓库，但无法加入第 $i$ 个歹徒的物品。每个数字均对 $167772161$ 取模。

样例

样例输入 1

3 3
2 2 1

样例输出 1

1 1
1 1
0 0

样例输入 2

5 5
1 2 3 4 5

样例输出 2

1 1 0 0
2 2 0 0
2 2 0 0
3 3 0 0
4 4 0 0