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.Exampleinput
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.
Solution:
private fun readLn() = readLine()!! // string line private fun readInt() = readLn().toInt() // single int private fun readLong() = readLn().toLong() // single long private fun readDouble() = readLn().toDouble() // single double private fun readStrings() = readLn().split(" ") // list of strings private fun readInts() = readStrings().map { it.toInt() } // list of ints private fun readLongs() = readStrings().map { it.toLong() } // list of longs private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles fun main(args: Array<String>) { var t = readInt() while (t-- > 0) { var n = readInt() var a = readInts() var s = 0 for (x in a) { s += maxOf(x, 0) } var t = CharArray(n) for (i in 0 until n) { t[i] = (if (a[i] > 0) '1' else '0') } var v = 787788 var who = -1 for (i in 0 until n) { if (a[i] > 0) { if (a[i] < v) { v = a[i] who = i } } if (a[i] < 0) { if (-a[i] < v) { v = -a[i] who = i } } } t[who] = (if (a[who] > 0) '0' else '1') println(s - v) println(t.joinToString("")) } }