在一个神秘的 OJ 上，小 C 曾经参加过 $n$ 场比赛，其中第 $i(i=1,2,\ldots,n)$ 场比赛获得了 $a_i$ 积分；积分可能是正的，可能是负的，但它一定是一个 $[-2, 2]$ 中的整数。

由于一些原因，小 C 会挑出一个区间的比赛 $[l, r]$，并和大家说：“要是我只打这个区间的比赛，那么我就有 $\sum_{i=l}^r a_i$ 分了！”当然，小 C 会挑选出至少一场比赛，而且选出区间的比赛积分总和是所有区间里最大的，而这个积分总和则是他对自己发挥的满意程度。

随着时间的流逝，小 C 逐渐忘记了自己每场比赛的分数，也忘了他对这些比赛的满意程度，他只记得每种分数的比赛打了多少场，而小 C 想知道，他满意程度最小可能是多少。于是他来请求于你。

输入格式

本题有多组测试数据。

第一行一个正整数 $T$，表示数据组数。

下面 $T$ 行，每行 $c_{-2},c_{-1},c_0,c_1,c_2$ 五个非负整数，分别表示每种分数的比赛场数。你可以自行算出 $n=c_{-2}+c_{-1}+c_0+c_1+c_2$。

输出格式

每组测试数据输出两行。第一行一个整数，表示小 C 满意程度的可能最小值。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示达到此最小值的任意一种可能的比赛得分情况。

样例

input

1
1 1 0 2 2

output

3
1 -1 2 -2 1 2

限制与约定

令 $\sum n$ 表示一组数据中 $n$ 的总和。对所有数据，保证 $1 \le T \le 10000,1 \le n,\sum n \le 5 \times 10^5$。