Dream Team

3000ms

262144K

Description:

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:

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:

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.

Sample 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

Sample Output:

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.

Informação

Provedor Codeforces

Código CF1297C