为了庆祝儿童节，一位有 $k$ 个孩子的母亲来到商店购买糖果。商店里有 $n$ 盒糖果，第 $i$ 盒有 $w_i$ 颗糖果。母亲会选择购买其中的一些盒子，并将所有买来的盒子分给 $k$ 个孩子。每个孩子会收到若干（可能为零）个盒子，并计算他收到的糖果总数。假设第 $i$ 个孩子收到的糖果总数为 $c_i$，则不公平度定义为 $\sum_{i=1}^k c_i^2$。为了让所有孩子都开心，母亲总是会以最小化不公平度的方式分配盒子。注意，她不能打开任何盒子来调整其中的糖果数量。

母亲正在考虑购买哪些盒子，但她无法做出最终决定。请编写一个程序，帮助母亲尝试所有 $2^n - 1$ 种非空的购买方案，并计算出每种方案下的最小不公平度。注意，你只需要报告所有 $2^n - 1$ 种非空子集中最小不公平度的总和。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 50$)，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$ ($1 \le m \le n \le 20, n + m \le 23$)，分别表示盒子的数量和参数 $m$。 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 50\,000$)，表示每个盒子中糖果的数量。

保证满足 $n > 12$ 的测试用例不超过 2 个。

输出格式

对于每个测试用例，输出 $m$ 行，第 $i$ 行 ($1 \le i \le m$) 包含一个整数，表示当 $k = i$ 时的答案。注意，答案可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

样例

输入 1

1
5 4
1 2 3 4 5

输出 1

2240
1180
930
884