Polycarp 是 IT 公司的项目经理。现在,他需要为他的团队选择开发人员来启动一个新项目。该公司有 $$$n$$$ 开发人员“坐在替补席上”(即不参与其他项目)。 Polycarp 评估了每个人的技能: $$$a_i$$$ ($$$-10^4 \le a_i \le 10^4$$$) — 第 $$$i$$$ 个开发人员的整数特征。该值可以是正值、零甚至负值(有些开发人员会造成干扰)。
Polycarp 为其团队选择一部分开发人员后,团队的实力将由所有选定开发人员的 $$$a_i$$$ 值的总和决定。
Polycarp担心,如果他以最大化$$$a_i$$$特征总和的方式选择团队,其他经理可能会觉得这是不可接受的。因此,他计划创建这样一个团队,使其 $$$a_i$$$ 值的总和严格小于最大可能值。
帮助波利卡普选择符合以下条件的团队:
- 所选团队的所有成员的特征 $$$a_i$$$ 的总和严格小于通过其他方式选择团队可以获得的最大值
- 同时,所选团队的所有成员的 $$$a_i$$$ 的特征总和尽可能最大。
如果按照上述要求,您可以通过多种方式选择团队,那么只需找到其中任何一种即可。
保证所需子集中的特征总和严格为正(即 Polycarp 始终可以选择非空团队)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例都以一行开头,其中包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — “替补”的开发人员数量。
测试用例的第二行包含整数序列 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^4 \le a_i \le 10^4$$$) — $$$n$$$ 开发人员的特征。保证特征使得答案中特征的总和严格为正。
保证输入中所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
按照给定 $$$t$$$ 测试用例在输入中出现的顺序打印答案。在每个答案的第一行,打印一个正整数 $$$s$$$ — 所需子集中的特征之和。第二行应仅包含字符 0 和 1 并与答案匹配:
- 如果第 $$$i$$$ 开发者属于团队,则第 $$$i$$$ 位置的字符应等于 1;
- 如果第 $$$i$$$ 开发人员不属于团队,则第 $$$i$$$ 位置的字符应等于 0。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
5 5 1 -1 1 -1 1 2 11 1 3 5 -3 4 3 5 3 -4 5 -1 0 3 -3 0
输出 #1
2 11101 11 10 6 111 5 100 2 10100
注意
在第一个测试用例中,最大子集 $$$a_1, a_3, a_5$$$ 的总和等于 $$$3$$$,因此 Polycarp 应该选择最大总和小于 $$$3$$$ 的团队。
在第二个测试用例中,最大子集 $$$a_1, a_2$$$ 的总和等于 $$$12$$$,因此 Polycarp 应选择最大总和小于 $$$12$$$ 的团队。
在第三个测试用例中,最大子集 $$$a_1, a_3$$$ 的总和等于 $$$9$$$。
在第四个测试用例中,最大子集 $$$a_1, a_2$$$ 的总和等于 $$$8$$$。
在第五个测试用例中,有几个子集的最大总和等于 $$$3$$$,因此 Polycarp 应该选择总和较低的团队。