Codeforces1138B Circus

http://codeforces.com/contest/1138/problem/B

Polycarp is a head of a circus troupe. There are nn — an even number — artists in the troupe. It is known whether the ii-th artist can perform as a clown (if yes, then ci=1ci=1, otherwise ci=0ci=0), and whether they can perform as an acrobat (if yes, then ai=1ai=1, otherwise ai=0ai=0).

Split the artists into two performances in such a way that:

• each artist plays in exactly one performance,
• the number of artists in the two performances is equal (i.e. equal to n2n2),
• the number of artists that can perform as clowns in the first performance is the same as the number of artists that can perform as acrobats in the second performance.

Input

The first line contains a single integer nn (2≤n≤50002≤n≤5000, nn is even) — the number of artists in the troupe.

The second line contains nn digits c1c2…cnc1c2…cn, the ii-th of which is equal to 11 if the ii-th artist can perform as a clown, and 00 otherwise.

The third line contains nn digits a1a2…ana1a2…an, the ii-th of which is equal to 11, if the ii-th artist can perform as an acrobat, and 00 otherwise.

Output

Print n2n2 distinct integers — the indices of the artists that should play in the first performance.

If there are multiple answers, print any.

If there is no solution, print a single integer −1−1.

Examples

input

Copy

4
0011
0101

output

Copy

1 4

input

Copy

6
000000
111111

output

Copy

-1

input

Copy

4
0011
1100

output

Copy

4 3

input

Copy

8
00100101
01111100

output

Copy

1 2 3 6

 

题意：n个人，c[i]表示是否可以当小丑，a[i]表示是否可以当演员。要求选出n/2个人第一天演出，剩下的n/2个人第二天演出，使得满足：第一天可以演小丑的人的个数等于第二天可以演演员的人个数。

思路：这个题比赛时候做不出来实在是不应该。

对于任意一个人（c[i],a[i]），只有四种状态：00，01，10，11。

我们对此分类，设第一天选四种状态的人数依次是a1,a2,a3,a4;第二天选四种状态 的人数依次是b1,b2,b3,b4。

写一个双重循环枚举a3和a4，11的人数减去a4就是b4，然后就确定了b2，进而确定了b1，然后确定a1。如果这个过程中ai，bi均合法，那么找到解，结束。

#include <bits/stdc++.h>
using namespace std;

int n;
char c[6000],a[6000];
int cnt[2][2];

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n;
	scanf("%s%s",c,a);
	for(int i=0;i<n;i++)cnt[c[i]-'0'][a[i]-'0']++;
	
	for(int a3=0;a3<=cnt[1][0];a3++)
	{
		for(int a4=0;a4<=cnt[1][1];a4++)
		{
			int b4=cnt[1][1]-a4;
			int b2=a3+a4-b4;
			if(b2<0||b2>cnt[0][1])continue;
			int a2=cnt[0][1]-b2;
			int a1=n/2-a2-a3-a4;
			if(a1<0||a1>cnt[0][0])continue;
			for(int i=0;i<n;i++)
			{
				if(a1&&c[i]=='0'&&a[i]=='0')printf("%d ",i+1),a1--;
				if(a2&&c[i]=='0'&&a[i]=='1')printf("%d ",i+1),a2--;
				if(a3&&c[i]=='1'&&a[i]=='0')printf("%d ",i+1),a3--;
				if(a4&&c[i]=='1'&&a[i]=='1')printf("%d ",i+1),a4--;
			}
			puts("");
			exit(0);
		}
	}
	puts("-1");
	exit(0);
}