问题 1309. -- 齐齐的宝藏

1309: 齐齐的宝藏

时间限制: 1 Sec  内存限制: 128 MB  Special Judge
提交: 153  解决: 83
[提交][状态][讨论版]

题目描述

天呐!优秀的wang9898趁齐齐出门打酱油的时间发现了齐齐珍藏的宝藏。然而想取得宝藏并不是件容易的事,齐齐早就给wang9898留下了一个谜题:
wang9898面前现在有n块宝石,一些为红宝石,一些为蓝宝石,第i块宝石上面标号为数字i,wang9898需要将这些宝石分为4组(记为G1,G2,G3,G4),并满足下面的条件
1. G1、G2全为红宝石,G3、G4全为蓝宝石
2. G1、G3的所有宝石序号之和等于G2、G4宝石序号之和
注:允许空组的存在
wang9898已经开启了这场赌局,如果他成功解开这个谜题,所有宝藏就归他所有,否则他将失去他gay wang的称号!
wang9898太想要这份宝藏了(太想保卫自己的称号了),你能帮帮他吗?

输入

第一行 一个正整数T ,表示有T组数据
对于每组数据
第一行 一个正整数n (1≤n≤1e5)
第二行 一个01字符串 第i个字符为0表示红宝石,为1表示蓝宝石

输出

对于每组数据,输出一个由{1,2,3,4}组成的字符串,第i个字符表示第i块宝石的组别
如果没有合法答案,则输出-1

样例输入

5
1
1
2
10
3
101
4
0000
7
1101001

样例输出

-1
-1
314
1221
3413214

提示

来源

[提交][状态][讨论版]