The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 3:

- Kotlin 1.4.0

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Dream Team

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarp 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.

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

Output

2 11101 11 10 6 111 5 100 2 10100

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2021 08:28:19 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|