CF1297C.Dream Team

Polycarp is the project manager in the IT-company. Right now, he needs to choose developers for his team to start a new project. The company has $n$ developers "on the bench" (i.e not involved in other projects). Polycarp assessed the skills of each of them: $a_i$ ($-10^4 \le a_i \le 10^4$) — an integer characteristic of the $i$-th developer. This value can be either positive, zero or even negative (some developers cause distractions).

After Polycarp chooses a subset of developers for his team, the strength of the team will be determined by the sum of $a_i$ values for all selected developers.

Polycarp fears that if he chooses a team in such a way that maximizes the sum of the characteristics of $a_i$, other managers may find this unacceptable. For this reason, he plans to create such a team that the sum of the $a_i$ values for it is strictly less than the maximum possible value.

Help Polycarp choose any team that:

• the sum of the characteristics $a_i$ for all members of the selected team is strictly less than the maximum value that can be achieved by choosing the team in some other way
• and at the same time, the sum of the characteristics of $a_i$ for all members of the selected team is the greatest possible.

If, following the requirements above, you can select a team in several ways, then just find any of them.

It's guaranteed that the sum of the characteristics in the desired subset is strictly positive (i.e. Polycarp can always choose a non-empty team).

波利卡普是一家IT公司的项目经理。目前，他需要为自己的团队挑选开发人员，以启动一个新项目。公司有 $n$ 名开发人员“待命”（即未参与其他项目）。波利卡普评估了每位开发人员的能力：$a_i$（$-10^4 \le a_i \le 10^4$）——表示第 $i$ 位开发人员的整数能力值。该值可以为正、零，甚至为负（某些开发人员反而会带来干扰）。

在波利卡普为团队选定一组开发人员后，团队的实力将由所有被选中开发人员的 $a_i$ 值之和决定。

波利卡普担心，若他直接选择能使 $a_i$ 总和最大的团队，其他经理可能认为此举不可接受。因此，他计划组建一支团队，使其 $a_i$ 值之和严格小于可能达到的最大总和。

请帮助波利卡普选出任意一支满足以下条件的团队：

• 所选团队中所有成员的 $a_i$ 特征值之和严格小于通过其他方式选择团队所能达到的最大值；
• 同时，所选团队中所有成员的 $a_i$ 特征值之和是所有满足上一条件的方案中最大的。

若依据上述要求存在多种可行的团队选择方式，则任选其一即可。

题目保证：所求子集的特征值之和严格为正（即波利卡普总能选出一个非空团队）。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case begins with a line containing one integer $n$ ($2 \le n \le 10^5$) — the number of developers "on the bench".

The second line of a test case contains a sequence of integers $a_1, a_2, \dots, a_n$ ($-10^4 \le a_i \le 10^4$) — the characteristics of the $n$ developers. It is guaranteed that the characteristics are such that the sum of the characteristics in the answer is strictly positive.

It is guaranteed that the sum of $n$ over all test cases in the input doesn't exceed $10^5$.

第一行包含一个整数 $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$。

Print the answers for the given $t$ test cases in the order that they appear in the input. In the first line of each answer, print a positive integer $s$ — the sum of the characteristics in the desired subset. The second line should contain only the characters 0 and 1 and match the answer:

• the character in the $i$-th position should be equal to 1 if the $i$-th developer belongs to the team;
• the character in the $i$-th position should be equal to 0 if the $i$-th developer does not belong to the team.

If there are several answers, print any of them.

按输入中给出的 $t$ 个测试用例的顺序输出对应答案。在每个答案的第一行，输出一个正整数 $s$ —— 所选子集中的特征值之和。第二行仅包含字符 0 和 1，并符合以下要求：

• 第 $i$ 个位置上的字符应为 1，当且仅当第 $i$ 个开发者属于该团队；
• 第 $i$ 个位置上的字符应为 0，当且仅当第 $i$ 个开发者不属于该团队。

若存在多个可行答案，输出任意一个即可。

In the first test case, the maximum subset $a_1, a_3, a_5$ has a sum equal to $3$, so Polycarp should choose a team with the maximum total sum which is less than $3$.

In the second test case, the maximum subset $a_1, a_2$ has a sum equal to $12$, so Polycarp should choose a team with the maximum total sum which is less than $12$.

In the third test case, the maximum subset $a_1, a_3$ has a sum equal to $9$.

In the fourth test case, the maximum subset $a_1, a_2$ has a sum equal to $8$.

In the fifth test case, there are several subsets with a maximum sum equal to $3$, so Polycarp should choose a team with a lower total sum.

在第一个测试用例中，最大子集 $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 应选择总和更小的队伍。