Yor are given an array A of size n. You have to make another array B which must be a permutation of n. You also have to choose an integer k such that k>abs(Ai) for all i from 1 to n.
Here abs(x) = -x if x<0 and abs(x) = x if x>=0. A permutation of n is an array of size n such that all numbers from 1 to n appear in that array.
let S = A1kB1 + A2kB2 + A3kB3 + ... + AnkBn. You have to minimize S and make sure that S>=0. If minimum value of S occurs for multiple permutations then print the smallest one.
Array C is smaller than array D if for some i, C1=D1, C2=D2,...,Ci-1=Di-1 and Ci < Di
You don't need to print the value of S. You have to print the integer k and the array B.
Input
In the 1st line of input there will be an integer T (1<=T<=100), the number of test cases. In each of the test cases there will be an integer n (1<=n<=500) followed by n integers, the elements of array A, where -100<=Ai<=100, Ai≠0 (1<=i<=n).
Output
For each test case, If there is no answer then print -1.
Otherwise, print one integer, k, followed by n integers, the elements of array B. If multiple permutations yield same value of S then print the lexicographically smallest one.
Sample
| Input | Output |
|---|---|
2 6 1 2 3 -2 -1 -3 1 100 | 4 6 2 1 4 3 5 101 1 |
