You are given a binary string S of length 2\cdot N. 

A partition of string S into strings P and Q is said to be *valid* if:
Both P and Q are [subsequences] of S of length N;
Each character of string S belongs to exactly one subsequence out of P and Q;
Strings P and Q are NOT equal.
  
Let A denote the set of indices of S that belong to the subsequence P.

Find whether it is possible to make a *valid* partition of S.  
If it is possible, print the elements of array A, in increasing order. Otherwise, print -1.

------ Input Format ------ 

- Each test contains multiple test cases. The first line contains the number of test cases T. Description of the test cases follows.
- The first line of each test case contains a single integer N, where 2\cdot N is the length of the binary string.
- The second line of each test case contains the binary string S of length 2\cdot N.

------ Output Format ------ 

For each test case, if a *valid* partition exists, print N distinct indices A_{1}, A_{2}, \ldots, A_{N} (in increasing order).  
If no *valid* partition exists, print -1.  
If there are multiple solutions, print any.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$S$ consists of $0$ and $1$ only.
- It is guaranteed that the sum of $N$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
4
1
11
1
10
3
100000
3
100100

----- Sample Output 1 ------ 
-1
1
1 2 3
1 4 6

----- explanation 1 ------ 
Test case $1$: It can be proven that no valid partition exists.

Test case $2$: A valid partition is $P = 1$ and $Q = 0$. Here, $A = [1]$.

Test case $3$: A valid partition is $P = 100$ and $Q = 000$. Here, $A = [1, 2, 3]$.

Test case $4$: A valid partition is $P = 110$ and $Q = 000$. Here, $A = [1, 4, 6]$.

Source: codechef | Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc


Solutions:
for _ in range(int(input())):
	a = int(input())
	x = str(input())
	p = []
	n = 0
	if x.count('0') == 0 or x.count('1') == 0:
		p.append(-1)
	else:
		for i in range(len(x)):
			if x[i] == '1':
				p.append(i + 1)
			if x.count('1') == len(p) and len(p) == i + 1 and (i + 1 < a):
				for j in range(i + 2, a + 1):
					p.append(j)
			if len(p) == a:
				break
			elif len(p) == x.count('1'):
				k = a * 2
				for j in range(k - (a - len(p)) + 1, k + 1):
					p.append(j)
	for i in p:
		print(i, end=' ')
	print()