Dream Team
Contest: Kotlin Heroes: Episode 3
Tags: *special, greedy

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).

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
5
5
1 -1 1 -1 1
2
11 1
3
5 -3 4
3
5 3 -4
5
-1 0 3 -3 0

Example output:
2
11101
11
10
6
111
5
100
2
10100

Editorial:
It can be proven that there are only two configurations we need to consider:
• The subset with the maximum sum, but without the smallest positive element. It's possible if there are at least two positive elements in array $$$a$$$.
• The subset with the maximum sum, but with one extra negative element (obviously, it should be one with the lowest absolute value). It's possible if there is at least one negative element in array $$$a$$$.
We can check both configurations separately or simultaneously in linear time and choose the best one.
P.S.: It's not hard to prove that the configuration should have no more than one positive element being absent (since, in the other way, we can return other elements and make the answer better) comparing to the subset with maximal sum. In the same manner, the configuration should have no more than one extra negative element.