题干：

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

题目大意：给n个人，0表示女生，1表示男生，第i个人的权值是i。女生分两组G1,G2，男生分两组G3,,G4。现在要构造这n个人的分组，使得G1+G3=G2+G4。

解题报告：

换句话说，使其中女生中的一组与男生中的一组中权值的和等于总权值的一半。

不难发现，其实与男女生无关，我们只要将权值分成一半和一半，然后对于前一半这个集合，男生就塞进G3,女生就塞进G1就行了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
char s[MAX];
int bk[MAX];
int main()
{
	int t;
	cin>>t;
	while(t--) {
		ll n;
		scanf("%lld",&n);
		ll ans = (n+1)*n/2;
		scanf("%s",s+1);
		if(ans%2 == 1) {
			printf("-1\n");continue;
		}
		ll res = ans/2;
		//bk=1  代表放入  女1  男3 
		for(ll i = n; i>=1; i--) {
			if(res-i >= 0) {
				bk[i] = 1;res -= i;
			}
			else bk[i] = 0;
		}
		for(int i = 1; i<=n; i++) {
			if(s[i] == '1') {//男 
				if(bk[i] == 1) printf("3");
				else printf("4");
			}
			else {
				if(bk[i] == 1) printf("1");
				else printf("2");
			}
		}
		printf("\n"); 
	}


	return 0 ;
}