You are given a string S, each of whose characters is either '0', '1', or '?'.

The *badness* of a binary string is defined to be the (absolute) difference between the number of 1s and the number of 0s present in it. For example, 001 has badness |1-2| = 1 and 11111 has badness |5-0| = 5.

Your task is to replace every '?' present in S with either '0' or '1', such that the badness of the resulting binary string is minimized.

If there are multiple solutions, you may print any of them.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case contains two lines.
- The first line of each test case contains an integer N, the number of characters of the string S.
- The second line of each test case contains the string S, whose characters are either '0', '1', or '?'.

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

For each test case, print a single line containing the binary string you obtained by replacing each '?' with either '0' or '1' such that its badness is minimum.

If there are multiple possible strings that minimize badness, you may print any of them.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
- The sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
4
?101
4
??10
6
???111
5
1?0?1

----- Sample Output 1 ------ 
0101
1010
000111
11001

----- explanation 1 ------ 
Test Case $1$. There are only two possible strings that can be constructed - $1101$ and $0101$. $1101$ has badness $2$, and $0101$ has badness $0$. Thus, the only possible answer is $0101$.

Test Case $2$. There are four possible strings that can be made, namely $\{0010, 0110, 1010, 1110\}$. Their respective badness values are $\{2, 0, 0, 2\}$. The minimum value here is $0$, attained by both $0110$ and $1010$ - and so either of these strings is a valid answer.

Test Case $3$. There are eight possible strings, of which $000111$ is the only one with minimum badness (that being $0$).

Test Case $4$. There are four possible strings, out of which three of them ($10001$, $10011$, $11001$) have badness $1$, which is minimum. All three of them are possible answers.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Ad-hoc

Greedy algorithms


Solutions:
def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())

def main():
	ones = s.count('1')
	zeroes = s.count('0')
	rand = s.count('?')
	diff = abs(ones - zeroes)
	added_ones = 0
	added_zeroes = 0
	if ones < zeroes:
		added_ones = diff
		rand -= diff
	else:
		added_zeroes = diff
		rand -= diff
	if rand > 0:
		added_zeroes += rand // 2
		added_ones += rand - rand // 2
	ans = ''
	for ele in s:
		if ele == '?':
			if added_ones > 0:
				ans = ans + '1'
				added_ones -= 1
			else:
				ans = ans + '0'
		else:
			ans = ans + ele
	print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	main()


from distutils import extension
import sys
from math import gcd, sqrt, log10, log2, floor, ceil
from collections import deque, defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True

class SegmentTree:

	def __init__(self, arr):
		self.narr = [-1]
		narr = [-1]
		for l in rg(1, 2 * len(arr) + 1 + 1):
			self.narr.append(-1)
		self.arr = arr

	def buildTree(self, i, j, l):
		if i == j:
			self.narr[l] = self.arr[i]
			return self.arr[i]
		mid = (i + j) // 2
		lt = self.buildTree(self.narr, self.arr, i, mid, 2 * l)
		ri = self.buildTree(self.narr, self.arr, mid + 1, j, 2 * l + 1)
		self.narr[l] = lt + ri
		return lt + ri

	def rangeUpdate(self, i, j, L, R, l, val):
		mid = (i + j) // 2
		if L <= i and j <= R:
			self.narr[l] += val
			return
		if L <= i:
			self.rangeUpdate(i, mid, L, R, 2 * l, val)
		if mid + 1 <= R:
			self.rangeUpdate(mid + 1, j, L, R, 2 * l + 1, val)

	def rangeQuery(self, i, j, L, R, l):
		if L <= i and j <= R:
			return self.narr[l]
		mid = (i + j) // 2
		ans = 0
		if L <= mid:
			ans += self.rangeQuery(i, mid, L, R, 2 * l)
		if mid + 1 <= R:
			ans += self.rangeQuery(mid + 1, j, L, R, 2 * l + 1)
		return ans
mod = 1000000000 + 7
for _ in range(ii()):
	n = ii()
	s = ip()
	ones = s.count('1')
	zeros = s.count('0')
	ques = s.count('?')
	extones = 0
	extzero = 0
	if ones > zeros:
		extzero = min(abs(ones - zeros), ques)
		ques = ques - min(abs(ones - zeros), ques)
	elif ones < zeros:
		extones = min(abs(ones - zeros), ques)
		ques = ques - min(abs(ones - zeros), ques)
	if ques % 2 != 0:
		extones = extones + 1
	extones = extones + ques // 2
	extzero = extzero + ques // 2
	res = ''
	for k in s:
		if k == '?':
			if extones > 0:
				res = res + '1'
				extones = extones - 1
			else:
				res = res + '0'
		else:
			res = res + k
	print(res)