CONTINUE...?

DreamGrid has  classmates numbered from  to . Some of them are boys and the others are girls. Each classmate has some gems, and more specifically, the -th classmate has  gems.

DreamGrid would like to divide the classmates into four groups , ,  and  such that:

  • Each classmate belongs to exactly one group.

  • Both  and  consist only of girls. Both  and  consist only of boys.

  • The total number of gems in  and  is equal to the total number of gems in  and .

Your task is to help DreamGrid group his classmates so that the above conditions are satisfied. Note that you are allowed to leave some groups empty.

Input

There are multiple test cases. The first line of input is an integer  indicating the number of test cases. For each test case:

The first line contains an integer  () -- the number of classmates.

The second line contains a string  () consisting of 0 and 1. Let  be the -th character in the string . If , the -th classmate is a boy; If , the -th classmate is a girl.

It is guaranteed that the sum of all  does not exceed .

Output

For each test case, output a string consists only of {1, 2, 3, 4}. The -th character in the string denotes the group which the -th classmate belongs to. If there are multiple valid answers, you can print any of them; If there is no valid answer, output "-1" (without quotes) instead.

Sample Input

5
1
1
2
10
3
101
4
0000
7
1101001

Sample Output

-1
-1
314
1221
3413214
有些关键信息无非复制。。。没办法大家理解一下
本题题意即为把[1,n]的数放入4个集合中，满足G1+G3=G2+G4，并且有一个01序列与序列1 2 3 4 ....n相匹配，其中0表示此位所代表的值只能放入G1或G2而1代表值放入G3或者G4中。如果存在这样的序列输出
1到N序列中每个元素对应装入G的下标。
其实简化一下，本题题意就是把1到N数表示为  某些数相加等于另外某些数    
我们可以写一下
 3：1+2=3；
 4：1+4=2+3；
 5：无法写出
 6：无法写出
 7：1+3+4+6=2+5+7
 8：1+8+2+7=3+6+4+5
 为什么5 6无非写出呢？我们发现里面有奇数个奇数，而这样必然会让一边为奇数一边为偶数肯定不行，因此（N%4<=2 && N%4!=0）输出-1；
 我们再分N%=2和N%2=1
 当N%2==0的时候只可能是N%4==0的情况。。。因为我们淘汰了N%4==2的情况，这样N只需要前后匹配即可
 当N%2==1的时候，我又找了一波规律如何奇数个组合 
  我发现
7：1+3+4+6=2+5+7
11:1+3+5+6+8+10=2+4+7+9+11==33(不信可以算算)
于是我发现。。。貌似len/2之前的奇数位和len/2之后的偶数位相加，等于len/2之前的偶数位加len/2的奇数位
于是我们就能解决把1到N的数组合并且相加成等式的问题了，最后只需要把01分组即可
AC代码
 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 int main()
 6 {
 7     int t,n,len;
 8     char a[100050];
 9     int  b[100050];
10     scanf("%d",&t);
11     while(t--)
12     {
13         scanf("%d",&n);
14         getchar();
15         scanf("%s",&a);
16         len=strlen(a);
17         if ((n%4)<=2 && n%4!=0)
18         {
19             printf("-1\n");
20         }
21         else
22         {
23             if(n%2==0)
24             {
25                 for(int i=0; i<len/4; i++)
26                 {
27                     if (a[i]=='1')printf("3");
28                     else printf("1");
29                 }
30                 for (int i=len/4; i<len-len/4; i++)
31                 {
32                     if (a[i]=='1')printf("4");
33                     else printf("2");
34                 }
35                 for (int i=len-len/4; i<len; i++)
36                 {
37                     if (a[i]=='1')printf("3");
38                     else printf("1");
39                 }
40                 printf("\n");
41             }
42             else
43             {
44                 for(int i=0; i<len/2; i++)
45                 {
46                     if (a[i]=='1')
47                     {
48                         if ((i+1)%2==1)printf("3");
49                         else printf("4");
50                     }
51                     if (a[i]=='0')
52                     {
53                         if ((i+1)%2==1)printf("1");
54                         else printf("2");
55                     }
56                 }
57                 for(int i=len/2; i<len; i++)
58                 {
59                     if (a[i]=='1')
60                     {
61                         if ((i+1)%2==1)printf("4");
62                         else printf("3");
63                     }
64                     if (a[i]=='0')
65                     {
66                         if ((i+1)%2==1)printf("2");
67                         else printf("1");
68                     }
69                 }
70                 printf("\n");
71             }
72         }
73     }
74     return 0;
75 }