题目描述

有 $n$ 户（编号依次为 $1,2,3,...,n$）共用一口井，已知井深不超过 $h$ 米。每户的绳长各不相同，而且以厘米为单位的绳长一定是整数。

有趣的是，下面的 $n$ 种情况都满足从井口放下绳索正好达到水面时：

• 编号为 $1$ 家的绳 $n_1$ 条接上编号为 $2$ 家的绳 $1$ 条；
• 编号为 $2$ 家的绳 $n_2$ 条接上编号为 $3$ 家的绳 $1$ 条；
• 编号为 $3$ 家的绳 $n_3$ 条接上编号为 $4$ 家的绳 $1$ 条；
• ……
• 编号为 $i$ 家的绳 $n_i$ 条接上编号为 $(i+1)$ 家的绳 $1$ 条；
• ……
• 编号为 $(n-1)$ 家的绳 $n_{n-1}$ 条接上编号为 $n$ 家的绳 $1$ 条；
• 编号为 $n$ 家的绳 $n_n$ 条接上编号为 $1$ 家的绳 $1$ 条；

现提供 $n,h$ 和题目描述中的 $n_1,n_2,n_3,...,n_{n-1},n_{n}$，问井深和各家绳长。

输入格式

第一行是一个正整数 $N$，表示有 $N$ 组测试数据。从第 $2$ 行开始依次是每组测试数据。

每组测试数据有 $2$ 行，第一行是两个正整数 $n,h$；第二行是 $n$ 个正整数 $n_1,n_2,n_3,...,n_{n-1},n_{n}$。

输入时，所有的整数之间用一个空格隔开。

输出格式

一共有 $N$ 行，依次是每组测试数据的计算结果。

对于每组测试数据：

• 如果找到了可行解，就输出 $n+1$ 个整数，依次是井的深度和每户的绳长（单位都是厘米）。如果有多组可行解，输出井的深度最小的那组解。所有的整数之间用一个空格隔开。
• 如果不存在可行解，就输出一行：not found。

输入输出样例

3
5 10
2 3 4 5 6
4 10
3 4 5 6
3 10
9 9 9

721 265 191 148 129 76
359 95 74 63 44
not found

说明/提示

👀️ 对于$100\%$ 的数据，$1 \leq N \leq 1000,1 \leq n \leq 20，1 \leq h \leq 10，1 \leq n_i \leq 10$。