Given a string containing of 0, 1 and ? - a wildcard character, generate all distinct binary strings that can be formed by replacing each wildcard character by either 0 or 1.
Example 1:
Input: 1??0?101
Output: 10000101 10001101 10100101 10101101 
11000101 11001101 11100101 11101101
Explanation:
There will be 8 such possible strings that 
can be formed, they are 10000101, 10001101, 
10100101, 10101101, 11000101, 11001101, 
11100101 and 11101101.
Example 2:
Input: 10?
Output: 100 101
Explanation: There are 2 such possible strings
and they are 100 and 101.
Your Task:
You don't need to read or print anything. Your task is to complete the function generate_binary_string() which takes the given string as input parameter and returns a vector of strings containing all the possible strings that can be formed.
Note : Strings should be printed in lexicographically increasing order.
Expected Time complexity: O(2^{n})
Expected Space complexity: O(n*2^{n})
Constraints:
1 ≤ length of string ≤ 30
Note: Number of '?' in any string does not exceed 15.

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3





class Solution:

    def generate_binary_string(self,s):

        # Code here

Solutions:
class Solution:

	def generate_binary_string(self, s):
		result = []

		def generateStringsHelper(s, idx, current):
			if idx == len(s):
				result.append(current)
				return
			if s[idx] == '?':
				generateStringsHelper(s, idx + 1, current + '0')
				generateStringsHelper(s, idx + 1, current + '1')
			else:
				generateStringsHelper(s, idx + 1, current + s[idx])
		generateStringsHelper(s, 0, '')
		return result


class Solution:

	def generate_binary_string(self, s):
		string_list = []

		def recurse(str):
			for (i, c) in enumerate(str):
				if c == '?':
					for r in ['0', '1']:
						str[i] = r
						recurse(str.copy())
					break
			else:
				string_list.append(''.join(str))
		recurse(list(s))
		return string_list


class Solution:

	def generate_binary_string(self, s):
		freq = s.count('?')
		count = 2 ** freq
		arr = [s] * count
		flag = 0
		for x in range(len(s)):
			if s[x] == '?':
				for y in range(count):
					tmp = str(format(y, 'b')).rjust(freq, '0')
					arr[y] = arr[y][:x] + tmp[flag] + arr[y][x + 1:]
				flag += 1
		return arr


class Solution:

	def generate_binary_string(self, Str):
		res = []
		result = []
		res.append(Str)
		while len(res) > 0:
			Str = res[0]
			if '?' in Str:
				ind = Str.index('?')
			else:
				ind = -1
			if ind != -1:
				s1 = Str.replace('?', '0', 1)
				res.append(s1)
				s2 = Str.replace('?', '1', 1)
				res.append(s2)
			else:
				result.append(Str)
			res.pop(0)
		return result


class Solution:

	def generate_binary_string(self, s):
		res = []
		arr = []
		sList = []
		for i in range(len(s)):
			if s[i] == '?':
				arr.append(i)
			sList.append(s[i])
		n = len(arr)
		r = pow(2, n)
		for i in range(r):
			fmt = '{:0{}b}'.format(i, n)
			for j in range(n):
				ind = int(arr[j])
				sList[ind] = fmt[j]
			res.append(''.join(sList))
		return res


class Solution:

	def generate_binary_string(self, s):
		arr = []
		sArr = []
		sList = []
		for k in range(len(s)):
			if s[k] == '?':
				sArr.append(k)
			sList.append(s[k])
		n = len(sArr)
		rng = pow(2, n)
		for i in range(rng):
			fmt = '{:0{}b}'.format(i, n)
			for f in range(n):
				ind = int(sArr[f])
				sList[ind] = fmt[f]
			arr.append(''.join(sList))
		return arr


class Solution:

	def binStrngs(self, pos, s, r, ans):
		if pos == len(s):
			ans.append(r)
			return
		if s[pos] != '?':
			self.binStrngs(pos + 1, s, r + s[pos], ans)
		else:
			self.binStrngs(pos + 1, s, r + '0', ans)
			self.binStrngs(pos + 1, s, r + '1', ans)

	def generate_binary_string(self, s):
		ans = []
		self.binStrngs(0, s, '', ans)
		return ans


class Solution:

	def generate_binary_string(self, s):
		l = []
		q = [s]
		while q:
			cur = q.pop(0)
			if '?' in cur:
				q.append(cur.replace('?', '0', 1))
				q.append(cur.replace('?', '1', 1))
			else:
				l.append(cur)
		return l


class Solution:

	def helper(self, pos, s, res, ans):
		if pos == len(s):
			ans.append(res)
			return
		if s[pos] != '?':
			self.helper(pos + 1, s, res + s[pos], ans)
		else:
			self.helper(pos + 1, s, res + '0', ans)
			self.helper(pos + 1, s, res + '1', ans)

	def generate_binary_string(self, s):
		ans = []
		self.helper(0, s, '', ans)
		return ans


class Solution:

	def generate_binary_string(self, s):
		a = []
		q = []
		t = []
		for i in range(len(s)):
			if s[i] == '?':
				q.append(i)
			t.append(s[i])
		n = len(q)
		r = pow(2, n)
		for i in range(r):
			f = '{:0{}b}'.format(i, n)
			for j in range(n):
				m = int(q[j])
				t[m] = f[j]
			a.append(''.join(t))
		return a


def rec(s, i, res, ans):
	if i == len(s):
		ans.append(res)
		return
	if s[i] == '?':
		rec(s, i + 1, res + '0', ans)
		rec(s, i + 1, res + '1', ans)
	else:
		rec(s, i + 1, res + s[i], ans)

class Solution:

	def generate_binary_string(self, s):
		res = []
		rec(s, 0, '', res)
		return res


class Solution:

	def generate_binary_string(self, s):
		n = s.count('?')
		arr = []
		for i in range(2 ** n):
			temp = bin(i)[2:]
			temp = (n - len(temp)) * '0' + temp
			arr.append(temp)
		ans = []
		for i in range(2 ** n):
			j = 0
			temp = ''
			for k in range(len(s)):
				if s[k] == '?':
					temp += arr[i][j]
					j += 1
				else:
					temp += s[k]
			ans.append(temp)
		return ans


class Solution:

	def generate_binary_string(self, s):
		n = s.count('?')
		l = [(n - len(bin(i)[2:])) * '0' + bin(i)[2:] for i in range(2 ** n)]
		ans = []
		for ele in l:
			new = ''
			i = 0
			for ch in s:
				if ch != '?':
					new += ch
				else:
					new += ele[i]
					i += 1
			ans.append(new)
		return ans


class Solution:

	def __init__(self):
		self.solution = []

	def dfs(self, s, i):
		if i == len(s):
			self.solution.append(s)
			return
		if s[i] == '?':
			(op1, op2) = (s, s)
			op1 = op1[0:i] + '0' + op1[i + 1:]
			op2 = op1[0:i] + '1' + op1[i + 1:]
			self.dfs(op1, i + 1)
			self.dfs(op2, i + 1)
		else:
			self.dfs(s, i + 1)

	def generate_binary_string(self, s):
		self.dfs(s, 0)
		return self.solution


class Solution:

	def generate_binary_string(self, s):
		ls1 = []
		cnt = s.count('?')
		for i in range(pow(2, cnt)):
			no = bin(i).replace('0b', '')
			if len(no) < cnt:
				n = cnt - len(no)
				x = '0' * n
				no = x + no
			st1 = s
			for j in range(cnt):
				st1 = st1.replace('?', no[j], 1)
			ls1.append(st1)
		return ls1


class Solution:

	def generate_binary_string(self, s):
		indeces = []
		n = len(s)
		for i in range(n):
			if s[i] == '?':
				indeces.append(i)
		indeces.reverse()
		output = []
		stack = [(s, indeces)]
		while stack:
			(string, arr) = stack.pop()
			if not arr:
				output.append(string)
				continue
			i = arr.pop()
			stack.append((string[:i] + '1' + string[i + 1:], arr.copy()))
			stack.append((string[:i] + '0' + string[i + 1:], arr.copy()))
		return output


class Solution:

	def generate_binary_string(self, s):
		res = set()
		pos = s.find('?')
		if pos == -1:
			res.add(s)
		else:
			res |= set(self.generate_binary_string(s[:pos] + '0' + s[pos + 1:]))
			res |= set(self.generate_binary_string(s[:pos] + '1' + s[pos + 1:]))
		return sorted(res)


class Solution:

	def getBinaryString(self, i, count):
		return '{0:b}'.format(i).zfill(count)

	def generate_binary_string(self, s):
		count = 0
		pos = []
		for (index, ch) in enumerate(s):
			if ch == '?':
				count += 1
				pos.append(index)
		lis = []
		for i in range(0, 2 ** count):
			string = self.getBinaryString(i, count)
			innerCount = 0
			newString = s
			for (index, ch) in enumerate(s):
				if ch == '?':
					newString = newString[0:index] + string[innerCount] + (newString[index + 1:len(s)] if index < len(s) - 1 else '')
					innerCount += 1
			lis.append(newString)
		return lis


class Solution:

	def _print(self, s, index, all_strs):
		if index == len(s):
			str = ''.join(s)
			all_strs.append(str)
			return all_strs
		if s[index] == '?':
			s[index] = '0'
			self._print(s, index + 1, all_strs)
			s[index] = '1'
			self._print(s, index + 1, all_strs)
			s[index] = '?'
		else:
			self._print(s, index + 1, all_strs)
		return all_strs

	def generate_binary_string(self, s):
		s = list(s)
		all_strs = []
		result = self._print(s, 0, all_strs)
		return result


class Solution:

	def generate_binary_string(self, s):
		s = s.split('?')
		return sorted(self.getOutput(s))

	def getOutput(self, s):
		if len(s) == 1:
			return s
		output = []
		for x in self.getOutput(s[1:]):
			output.append(s[0] + '0' + x)
			output.append(s[0] + '1' + x)
		return output


class Solution:

	def generate_binary_string(self, s):
		res = ['']
		for i in s:
			temp = []
			if i == '?':
				for j in res:
					temp.append(j + '0')
					temp.append(j + '1')
			else:
				for j in res:
					temp.append(j + i)
			res = temp[:]
		res.sort()
		return res


class Solution:

	def generate_binary_string(self, s):
		l = list(s)
		ans = []
		ans = self.helper(0, l, ans)
		ans.sort()
		return ans

	def helper(self, index, s, ans):
		if index == len(s):
			ans.append(''.join(s))
			return ans
		if s[index] == '?':
			s[index] = '0'
			ans = self.helper(index + 1, s, ans)
			s[index] = '1'
			ans = self.helper(index + 1, s, ans)
			s[index] = '?'
		else:
			ans = self.helper(index + 1, s, ans)
		return ans


import copy

class Solution:

	def generate_binary_string(self, s):
		res = []

		def recurse(s, i, acc):
			if i >= len(s):
				res.append(acc)
				return
			if s[i] != '?':
				acc += s[i]
				recurse(s, i + 1, acc)
			else:
				recurse(s, i + 1, acc + '0')
				recurse(s, i + 1, acc + '1')
				return
		recurse(s, 0, '')
		finalRes = []
		return res


class Solution:

	def generate_binary_string(self, s):
		v = []

		def f(i, s, t):
			if i == len(s):
				v.append(t)
				return
			if s[i] == '?':
				f(i + 1, s, t + '0')
				f(i + 1, s, t + '1')
			else:
				f(i + 1, s, t + s[i])
		f(0, s, '')
		return v


class Solution:

	def generate_binary_string(self, s):
		index = []
		ans = []
		n = len(s)
		for i in range(n):
			if s[i] == '?':
				index.append(i)

		def generateAllBinaryStrings(n, arr, i):
			if i == n:
				gen_s = list(s)
				for j in range(n):
					gen_s[index[j]] = arr[j]
				ans.append(''.join(map(str, gen_s)))
				return
			arr[i] = 0
			generateAllBinaryStrings(n, arr, i + 1)
			arr[i] = 1
			generateAllBinaryStrings(n, arr, i + 1)
		n = len(index)
		arr = [None] * n
		generateAllBinaryStrings(n, arr, 0)
		return ans


class Solution:

	def generate_binary_string(self, s):
		n = s.count('?')
		filler = []
		indexes = []
		res = []
		for i in range(len(s)):
			if s[i] == '?':
				indexes.append(i)
		prefix = '{0:0' + str(n) + 'b}'
		for i in range(2 ** n):
			filler.append(prefix.format(i))
		for fill in filler:
			temp = list(s[:])
			for (idx, f) in zip(indexes, fill):
				temp[idx] = f
			res.append(''.join(temp))
		return res


import collections

class Solution:

	def generate_binary_string(self, s):
		q = collections.deque([])
		q.append(s)
		ans = []
		while q:
			s2 = q.popleft()
			try:
				idx = s2.index('?')
			except:
				idx = -1
			if idx != -1:
				s0 = s2.replace('?', '0', 1)
				s1 = s2.replace('?', '1', 1)
				q.append(s0)
				q.append(s1)
			else:
				ans.append(s2)
		return ans


class Solution:

	def __init__(self):
		self.res = []

	def work(self, s):
		if '?' in s:
			s1 = s.replace('?', '0', 1)
			s2 = s.replace('?', '1', 1)
			self.generate_binary_string(s1)
			self.generate_binary_string(s2)
		else:
			self.res.append(s)

	def generate_binary_string(self, s):
		self.work(s)
		return self.res


class Solution:

	def generate_binary_string(self, s):
		n = 0
		il = []
		for i in range(0, len(s)):
			if s[i] == '?':
				il.append(i)
				n += 1
		l = ['0' * (n - len(bin(i)[2:])) + bin(i)[2:] for i in range(0, 2 ** n)]
		res = []
		s = list(s)
		for num in l:
			for i in range(0, n):
				s[il[i]] = num[i]
			res.append(''.join(s))
		return res


class Solution:

	def generate_binary_string(self, S):
		s = list(S)
		bin_list = []
		count = s.count('?')
		for i in range(2 ** count):
			bin_list.append(bin(i)[2:])
		for i in range(len(bin_list)):
			l = len(bin_list[i])
			bin_list[i] = (count - l) * '0' + bin_list[i]
		result = []
		for elm in bin_list:
			j = 0
			for k in range(len(s)):
				if s[k] == '?':
					s[k] = elm[j]
					j += 1
			result.append(''.join(s))
			s = list(S)
		return result


class Solution:

	def generate_binary_string(self, s):
		return self.get_combinations(s, 0, len(s))

	def get_combinations(self, string, index, n):
		if index == n:
			return ['']
		char = string[index]
		possibilities = self.get_combinations(string, index + 1, n)
		res = []
		current_index_characters = [char]
		if char == '?':
			current_index_characters = ['0', '1']
		for i in current_index_characters:
			for combination in possibilities:
				res.append(i + combination)
		return res


class Solution:

	def generate_binary_string(self, s):
		res = []
		count = 0
		res.append(s)
		for i in res:
			if '?' in i:
				newi = i.replace('?', '0', 1)
				newi2 = i.replace('?', '1', 1)
				res.append(newi)
				res.append(newi2)
				count += 1
		result = [i for i in res[count:]]
		return result


class Solution:

	def generate_binary_string(self, s):
		left = ''
		right = ''
		res = []
		orig = s
		res = self.solve(left, right, 0, res, orig)
		return res

	def solve(self, left, right, i, res, s):
		if i >= len(s):
			if left != '' and right != '':
				send = left + right
				res.append(send)
			elif left != '':
				send = left
				res.append(send)
			elif right != '':
				send = right
				res.append(send)
			else:
				res.append(s)
			return res
		if s[i] == '?':
			left = s[0:i]
			if i + 1 < len(s):
				right1 = '0' + s[i + 1:]
				right2 = '1' + s[i + 1:]
			else:
				right1 = '0'
				right2 = '1'
			res = self.solve(left, right1, i + 1, res, left + right1)
			res = self.solve(left, right2, i + 1, res, left + right2)
			return res
		else:
			return self.solve(left, right, i + 1, res, s)


def genString(st, index, currSt, ans):
	if len(currSt) == len(st):
		ans.append(currSt)
		return
	elif st[index] == '?':
		genString(st, index + 1, currSt + '0', ans)
		genString(st, index + 1, currSt + '1', ans)
	else:
		genString(st, index + 1, currSt + st[index], ans)
	return ans

class Solution:

	def generate_binary_string(self, s):
		op = genString(s, 0, '', [])
		return op


class Solution:

	def getIndex(self, string, n):
		for i in range(n):
			if string[i] == '?':
				return i
		return -1

	def generate_binary_string(self, s):
		q = []
		q.append(s)
		n = len(s)
		while len(q) > 0:
			temp = q[0]
			index = self.getIndex(temp, n)
			if index == -1:
				break
			s1 = temp.replace('?', '0', 1)
			q.append(s1)
			s2 = temp.replace('?', '1', 1)
			q.append(s2)
			q.pop(0)
		return q


class Solution:

	def perm(self, c, n, t, s, l):
		if c == n - 1:
			if s[c] != '?':
				l.append(t + s[c])
			else:
				l.append(t + '0')
				l.append(t + '1')
			return
		if s[c] != '?':
			self.perm(c + 1, n, t + s[c], s, l)
		else:
			self.perm(c + 1, n, t + '0', s, l)
			self.perm(c + 1, n, t + '1', s, l)

	def generate_binary_string(self, s):
		l = []
		self.perm(0, len(s), '', s, l)
		l.sort()
		return l


class Solution:

	def generate_binary_string(self, s):
		res = []
		self.backtrack('', res, s)
		return res

	def backtrack(self, path, res, s):
		if len(path) == len(s):
			res.append(path)
			return
		curChar = s[len(path)]
		if curChar == '?':
			self.backtrack(path + '0', res, s)
			self.backtrack(path + '1', res, s)
		else:
			self.backtrack(path + curChar, res, s)


class Solution:

	def helper(self, s, index, ans):
		if index == len(s):
			ans.append(''.join(s))
			return
		if s[index] == '?':
			s[index] = '0'
			self.helper(s, index + 1, ans)
			s[index] = '1'
			self.helper(s, index + 1, ans)
			s[index] = '?'
		else:
			self.helper(s, index + 1, ans)

	def generate_binary_string(self, s):
		list1 = [i for i in s]
		ans = []
		self.helper(list1, 0, ans)
		return ans


class Solution:

	def generate_binary_string(self, s):
		num_q = len([ch for ch in s if ch == '?'])
		result = []
		max_num = 2 ** num_q - 1
		num = 0
		while num <= max_num:
			bin_s = str(bin(num + 2 ** num_q))[3:]
			count = 0
			ss = s
			for i in range(len(s)):
				if s[i] == '?':
					ss = ss[:i] + bin_s[count] + ss[i + 1:]
					count += 1
			result.append(ss)
			num += 1
		return result


class Solution:

	def generate_binary_string(self, string):

		def get_comb(string, index):
			n = len(string)
			if index == n:
				return ['']
			returnedRes = get_comb(string, index + 1)
			res = []
			for ele in returnedRes:
				if string[index] == '?':
					res.append('0' + ele)
					res.append('1' + ele)
				else:
					res.append(string[index] + ele)
			return res
		ans = get_comb(string, 0)
		anss = sorted(ans, key=str)
		return anss


class Solution:

	def generate_binary_string(self, s):
		ans = []

		def dfs(index, binary):
			if index == len(s):
				ans.append(binary)
				return
			if s[index] != '?':
				dfs(index + 1, binary + s[index])
			else:
				dfs(index + 1, binary + '0')
				dfs(index + 1, binary + '1')
		dfs(0, '')
		return ans


class Solution:

	def generate_binary_string(self, s):

		def rec(ind, S, tem, n):
			if ind == n:
				out.append(tem)
				return
			if S[ind] == '?':
				rec(ind + 1, S, tem + '1', n)
				rec(ind + 1, S, tem + '0', n)
			else:
				tem += S[ind]
				rec(ind + 1, S, tem, n)
		global out
		out = []
		rec(0, s, '', len(s))
		out.sort()
		return out


class Solution:

	def generate_binary_string(self, s):
		self.ans = []
		n = len(s)
		self.recu(s, n, '', 0)
		return self.ans

	def recu(self, s, n, output, i):
		if i == n:
			self.ans.append(output)
			return
		if s[i] == '?':
			output = output + '0'
			self.recu(s, n, output, i + 1)
			output = output[:-1]
			output = output + '1'
			self.recu(s, n, output, i + 1)
		else:
			output = output + s[i]
			self.recu(s, n, output, i + 1)


class Solution:

	def generate_binary_string(self, s):
		ct = 0
		ar = []
		result = []
		for it in s:
			if it == '?':
				ct += 1
		total = pow(2, ct)
		for i in range(total):
			val = '{0:b}'.format(i)
			add = ct - len(val)
			temp = ''
			for i in range(add):
				temp += '0'
			val = temp + val
			ar.append(val)
		for it in ar:
			temp = ''
			i = 0
			for st in s:
				if st == '?':
					temp += it[i]
					i += 1
				else:
					temp += st
			result.append(temp)
		return result


class Solution:

	def generate_binary_string(self, S):
		if len(S) == 0:
			return [S]
		agg = []
		for i in range(len(S)):
			if S[i] == '?':
				suboptions = self.generate_binary_string(S[i + 1:])
				for s in suboptions:
					agg.append(S[:i] + '0' + s)
					agg.append(S[:i] + '1' + s)
				return sorted(agg)
		return [S]


from collections import deque

class Solution:

	def generate_binary_string(self, s):
		l = []
		n = len(s)
		q = deque()
		q.append('')
		for i in range(n):
			size = len(q)
			while size > 0:
				str = q.popleft()
				size = size - 1
				if s[i] == '?':
					q.append(str + '0')
					q.append(str + '1')
				else:
					q.append(str + s[i])
		while q:
			l.append(q.popleft())
		return l


class Solution:

	def generate_binary_string(self, s):
		r = []

		def generate_binary_string_helper(s, beg_str=''):
			if len(beg_str) == len(s):
				return [beg_str]
			else:
				r = []
				if s[len(beg_str)] in ['0', '1']:
					r += generate_binary_string_helper(s, beg_str + s[len(beg_str)])
				else:
					r += generate_binary_string_helper(s, beg_str + '0')
					r += generate_binary_string_helper(s, beg_str + '1')
				return r
		return generate_binary_string_helper(s)


class Solution:

	def generate_binary_string(self, s):
		missing_arr = [i for i in range(len(s)) if s[i] == '?']
		if len(missing_arr) == 0:
			return [s]
		n = len(missing_arr)
		m = 2 ** n
		output_arr = []
		for i in range(m):
			b = str(bin(i))[2:]
			b = '0' * (n - len(b)) + b
			temp_s = list(s)
			for (j, idx) in enumerate(missing_arr):
				temp_s[idx] = b[j]
			output_arr.append(''.join(temp_s))
		return output_arr


class Solution:

	def generate_binary_string(self, s):
		li = list(s)
		pos = []
		ans = []
		for i in range(len(s)):
			if s[i] == '?':
				pos.append(i)

		def bins(li, ind):
			if ind == len(pos):
				ans.append(''.join(li))
				return
			li[pos[ind]] = '0'
			bins(li, ind + 1)
			li[pos[ind]] = '1'
			bins(li, ind + 1)
		bins(li, 0)
		return ans


class Solution:

	def generate_binary_string(self, s):
		ind = []
		for i in range(len(s)):
			if s[i] == '?':
				ind.append(i)
		ans = []
		n = len(ind)
		for i in range(2 ** n):
			b = bin(i)[2:]
			c = '0' * (n - len(b)) + b
			for j in range(n):
				s = s[:ind[j]] + c[j] + s[ind[j] + 1:]
			ans.append(s)
		return ans
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		ob = Solution()
		ans = ob.generate_binary_string(s)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def generate_binary_string(self, s):
		S = list(s)
		pos = []
		res = []
		for i in range(len(s)):
			if s[i] == '?':
				pos.append(i)
		count = len(pos)
		pos.reverse()
		j = 0
		for i in range(2 ** count):
			for k in range(count):
				if k >= len(bin(j)):
					c = '0'
				else:
					c = bin(j)[-(k + 1)]
				if c == 'b':
					c = '0'
				S[pos[k]] = c
			j += 1
			res.append(''.join(S))
		return res
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		ob = Solution()
		ans = ob.generate_binary_string(s)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def generate_binary_string(self, s):

		def genBin(s, i, l):
			if i == len(s):
				l.append(''.join(s.copy()))
				return
			if s[i] == '?':
				s[i] = '0'
				genBin(s, i + 1, l)
				s[i] = '1'
				genBin(s, i + 1, l)
				s[i] = '?'
			else:
				genBin(s, i + 1, l)
		l = []
		genBin(list(s), 0, l)
		l.sort()
		return l
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		ob = Solution()
		ans = ob.generate_binary_string(s)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def generate_binary_string(self, s):
		ans = [s]
		index = ans[-1].find('?')
		while index >= 0:
			temp = ans.pop(0)
			ans.append(temp[:index] + '0' + temp[index + 1:])
			ans.append(temp[:index] + '1' + temp[index + 1:])
			index = ans[0].find('?')
		return ans
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		ob = Solution()
		ans = ob.generate_binary_string(s)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def helper(self, pos, s, res, ans):
		if pos == len(s):
			ans.append(res)
			return
		if s[pos] != '?':
			self.helper(pos + 1, s, res + s[pos], ans)
		else:
			self.helper(pos + 1, s, res + '0', ans)
			self.helper(pos + 1, s, res + '1', ans)

	def generate_binary_string(self, s):
		ans = []
		self.helper(0, s, '', ans)
		return ans
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		ob = Solution()
		ans = ob.generate_binary_string(s)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def generate_binary_string(self, a):
		res = []

		def dfs(s):
			if '?' in s:
				s1 = s.replace('?', '0', 1)
				s2 = s.replace('?', '1', 1)
				dfs(s1)
				dfs(s2)
			else:
				res.append(s)
		dfs(a)
		return res
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		ob = Solution()
		ans = ob.generate_binary_string(s)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def generate_binary_string(self, s):
		global ans
		ans = []

		def helper(curr, idx):
			global ans
			while idx < len(curr) and curr[idx] != '?':
				idx += 1
			if idx == len(curr):
				ans.append(''.join(curr))
				return
			curr[idx] = '0'
			helper(curr, idx)
			curr[idx] = '1'
			helper(curr, idx)
			curr[idx] = '?'
		helper(list(s), 0)
		return ans
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		ob = Solution()
		ans = ob.generate_binary_string(s)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def generate_binary_string(self, s, strings=[]):
		strings = ['']
		s = s[::-1]
		for c in s:
			if c == '?':
				for (i, st) in zip(range(len(strings)), strings):
					strings.append('1' + st)
					strings[i] = '0' + st
			else:
				strings = [c + st for st in strings]
		return strings
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		ob = Solution()
		ans = ob.generate_binary_string(s)
		for i in ans:
			print(i, end=' ')
		print()


import re

class Solution:

	def generate_binary_string(self, s):
		a = [s]
		st = 0
		arr = []
		for _ in range(s.count('?')):
			st = s.find('?', st)
			arr.append(st)
			st += 1
		for i in reversed(arr):
			tmp = []
			for y in ['0', '1']:
				for x in a:
					tmp.append(x[:i] + y + x[i + 1:])
			a = tmp
		return a


class Solution:

	def generate_binary_string(self, s):
		ans = []
		n = len(s)

		def walk(i, t):
			if i == n:
				ans.append(t)
				return
			if s[i] in ['0', '1']:
				walk(i + 1, t + s[i])
			else:
				walk(i + 1, t + '0')
				walk(i + 1, t + '1')
		walk(0, '')
		return ans


class Solution:

	def generate_binary_string(self, s):
		res = []

		def recur(cur_ind, s, cur_str):
			nonlocal res
			if cur_ind == len(s):
				res += [cur_str]
				return
			cur = s[cur_ind]
			if cur == '1' or cur == '0':
				recur(cur_ind + 1, s, cur_str + cur)
			else:
				recur(cur_ind + 1, s, cur_str + '0')
				recur(cur_ind + 1, s, cur_str + '1')
		recur(0, s, '')
		return sorted(res)


class Solution:

	def generate_binary_string(self, s):

		def f(s, n, v):
			if n == 0:
				v.append(s)
				return
			s1 = s.replace('?', '0', 1)
			s2 = s.replace('?', '1', 1)
			f(s1, n - 1, v)
			f(s2, n - 1, v)
		v = []
		l = list(s)
		n = l.count('?')
		f(s, n, v)
		return v


class Solution:

	def generate_binary_string(self, s):
		res = []
		arr = list(s)

		def dfs(i, arr):
			if i >= len(s):
				res.append(''.join(arr))
				return
			if s[i] != '?':
				dfs(i + 1, arr)
			else:
				arr[i] = '0'
				dfs(i + 1, arr)
				arr[i] = '1'
				dfs(i + 1, arr)
		dfs(0, arr)
		return res


class Solution:

	def generate_binary_string(self, s):
		res = []

		def dfs(s, first):
			if first == len(s):
				res.append(s)
				return
			if s[first] == '?':
				s = s[:first] + '0' + s[first + 1:]
				dfs(s, first + 1)
				s = s[:first] + '1' + s[first + 1:]
				dfs(s, first + 1)
			else:
				dfs(s, first + 1)
		dfs(s, 0)
		return res


class Solution:

	def generate_binary_string(self, s):
		l = [s]
		loop = 1
		while loop:
			loop = 0
			n = len(l)
			for i in range(n):
				t = l.pop(0)
				ind = -1
				for x in range(len(t)):
					if t[x] == '?':
						ind = x
						break
				if ind != -1:
					loop = 1
					l.append(t[:ind] + '0' + t[ind + 1:])
					l.append(t[:ind] + '1' + t[ind + 1:])
				else:
					l.append(t)
		return sorted(l)


class Solution:

	def pnc(self, s, i, ans):
		j = 0
		for j in range(i + 1, len(s)):
			if s[j] == '?':
				break
		else:
			s = s[:i] + '0' + s[i + 1:]
			ans.append(s)
			s = s[:i] + '1' + s[i + 1:]
			ans.append(s)
			return
		s = s[:i] + '0' + s[i + 1:]
		self.pnc(s, j, ans)
		s = s[:i] + '1' + s[i + 1:]
		self.pnc(s, j, ans)

	def generate_binary_string(self, s):
		i = 0
		ans = []
		for i in range(0, len(s)):
			if s[i] == '?':
				break
		else:
			return [s]
		self.pnc(s, i, ans)
		return ans


class Solution:

	def generate_binary_string(self, s):

		def getans(idx, arr, ans):
			if idx == len(arr):
				val = ''
				for i in arr:
					val += i
				ans.append(val)
				return
			if arr[idx] == '?':
				for ch in '01':
					arr[idx] = ch
					getans(idx + 1, arr, ans)
					arr[idx] = '?'
			else:
				getans(idx + 1, arr, ans)
		ans = []
		arr = list(s)
		getans(0, arr, ans)
		return ans


class Solution:

	def generate_binary_string(self, s):

		def gen(s, index):
			nonlocal answer
			if index == len(s):
				answer.append(''.join(s))
				return
			if s[index] == '?':
				s[index] = '0'
				gen(s, index + 1)
				s[index] = '1'
				gen(s, index + 1)
				s[index] = '?'
			else:
				gen(s, index + 1)
		answer = []
		gen(list(s), 0)
		return answer


import itertools

class Solution:

	def generate_binary_string(self, s):
		variables = s.count('?')
		digits = [n for n in s]
		permutations = [seq for seq in itertools.product('01', repeat=variables)]
		results = []
		for permutation in permutations:
			count = 0
			binary = []
			for char in digits:
				if char == '?':
					binary.append(permutation[count])
					count += 1
				else:
					binary.append(char)
			results.append(''.join(binary))
		return results


class Solution:

	def recurr(s, qmap, key, inx):
		if inx > len(s) - 1:
			return ['']
		if key > len(qmap) - 1:
			return [''.join(s[inx:])]
		out = []
		st = ''.join(s[inx:qmap[key]])
		s[qmap[key]] = '0'
		exc = Solution.recurr(s.copy(), qmap, key + 1, qmap[key])
		for c in exc:
			out.append(st + c)
		s[qmap[key]] = '1'
		exc = Solution.recurr(s.copy(), qmap, key + 1, qmap[key])
		for c in exc:
			out.append(st + c)
		return out

	def generate_binary_string(self, s):
		binr = []
		mapf = []
		for i in range(len(s)):
			if s[i] == '?':
				mapf.append(i)
			binr.append(s[i])
		return Solution.recurr(binr, mapf, 0, 0)


class Solution:

	def generate_binary_string(self, s):
		from itertools import combinations
		n = len(s)
		l = []
		for i in range(n):
			if s[i] == '?':
				l.append(i)
		ans = []
		for i in range(len(l) + 1):
			for val in combinations(l, i):
				t = s
				for v in l:
					if v in val:
						t = t[:v] + '1' + t[v + 1:]
					else:
						t = t[:v] + '0' + t[v + 1:]
				ans.append(t)
		return sorted(ans)


def sol(s, ans):
	if '?' not in s:
		ans.append(s)
		return
	else:
		a = s[:]
		gg = list(a)
		for i in range(len(gg)):
			if gg[i] == '?':
				gg[i] = '0'
				break
		a = ''.join(gg)
		sol(a, ans)
		b = s[:]
		gg = list(b)
		for i in range(len(gg)):
			if gg[i] == '?':
				gg[i] = '1'
				break
		b = ''.join(gg)
		sol(b, ans)

class Solution:

	def generate_binary_string(self, s):
		ans = []
		sol(s, ans)
		return ans


class Solution:

	def generate_binary_string(self, s):
		wild_card_count = 0
		for char in s:
			if char == '?':
				wild_card_count += 1
		if wild_card_count == 0:
			return [s]

		def dfs(n):
			if n > wild_card_count:
				return ['']
			zeros = []
			ones = []
			combincations = dfs(n + 1)
			for combination in combincations:
				zeros.append('0' + combination)
			for combination in combincations:
				ones.append('1' + combination)
			return zeros + ones
		combinations = dfs(1)
		vector = []
		for comb in combinations:
			i = 0
			string = ''
			for char in s:
				if char != '?':
					string += char
				else:
					string += comb[i]
					i += 1
			vector.append(string)
		return vector


class Solution:

	def generate_binary_string(self, s):
		result = []

		def helper(s, curr, i):
			if i >= len(s):
				result.append(curr)
			elif s[i] == '0' or s[i] == '1':
				helper(s, curr + s[i], i + 1)
			else:
				helper(s, curr + '0', i + 1)
				helper(s, curr + '1', i + 1)
		helper(s, '', 0)
		return result


res = []

class Solution:

	def genBin(self, s):
		global res
		if '?' in s:
			s1 = s.replace('?', '0', 1)
			s2 = s.replace('?', '1', 1)
			self.genBin(s1)
			self.genBin(s2)
		else:
			res.append(s)
		return res

	def generate_binary_string(self, s):
		global res
		res = []
		result = self.genBin(s)
		result.sort()
		return result


class Solution:

	def generate_binary_string(self, s):
		found_Q = False
		n = len(s)
		for i in range(n - 1, -1, -1):
			if s[i] == '?':
				found_Q = True
				break
		if found_Q:
			if i == n - 1:
				s1 = s[:i] + '0'
				s2 = s[:i] + '1'
			else:
				s1 = s[:i] + '0' + s[i + 1:]
				s2 = s[:i] + '1' + s[i + 1:]
			lst1 = self.generate_binary_string(s1)
			lst2 = self.generate_binary_string(s2)
			return sorted(lst1 + lst2)
		else:
			return [s]


class Solution:

	def generate_binary_string(self, s):
		global found_strs
		found_strs = set()
		sl = list(s)
		self.generate_binary_string_sub(sl, 0)
		return sorted(found_strs)

	def generate_binary_string_sub(self, sl, i):
		n = len(sl)
		if i == n:
			global found_strs
			found_strs.add(''.join(sl))
			return
		if sl[i] == '?':
			sl[i] = '0'
			self.generate_binary_string_sub(sl, i + 1)
			sl[i] = '1'
			self.generate_binary_string_sub(sl, i + 1)
			sl[i] = '?'
		else:
			self.generate_binary_string_sub(sl, i + 1)