You are given a string $s$ of 0's and 1's. You are allowed to perform the following operation:

choose a non-empty contiguous substring of $s$ that contains an equal number of 0's and 1's;

flip all characters in the substring, that is, replace all 0's with 1's, and vice versa;

reverse the substring.

For example, consider $s$ = 00111011, and the following operation:

Choose the first six characters as the substring to act upon: 00111011. Note that the number of 0's and 1's are equal, so this is a legal choice. Choosing substrings 0, 110, or the entire string would not be possible.

Flip all characters in the substring: 11000111.

Reverse the substring: 10001111.

Find the lexicographically smallest string that can be obtained from $s$ after zero or more operations.


-----Input-----

The first line contains a single integer $T$ ($1 \leq T \leq 5 \cdot 10^5$) — the number of test cases. Each of the following $T$ lines contains a single non-empty string — the input string $s$ for the respective test case.

All strings consist of characters 0 and 1, and their total length does not exceed $5 \cdot 10^5$.


-----Output-----

For each test case, on a separate line print the lexicographically smallest string that can be obtained from $s$ after zero or more operations.


-----Examples-----

Input
3
100101
1100011
10101010
Output
010110
0110110
10101010


-----Note-----

In the first test case a single operation should be applied to the entire string.

In the second test case two operations are needed: 0111001, 0110110.

In the third test case the string stays the same after any operation.

Difficulty: VERY_HARD
Tags: Graph algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
import io, os, sys
input = sys.stdin.readline
print = sys.stdout.write
t = int(input())
START = 500001
seen = [0] * (2 * START)
while t > 0:
	t -= 1
	s = input().strip('\n')
	cur = START
	for c in s:
		if c == '0':
			seen[cur] += 1
			cur -= 1
		else:
			cur += 1
			seen[cur] += 1
	cur = START
	while True:
		if seen[cur] > 1 or (seen[cur] > 0 and seen[cur + 1] == 0):
			seen[cur] -= 1
			cur -= 1
			print('0')
		elif seen[cur + 1] > 0:
			cur += 1
			seen[cur] -= 1
			print('1')
		else:
			break
	print('\n')


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
START = 500001
seen = [0] * (2 * START)
while t > 0:
	t -= 1
	s = input()
	cur = START
	for c in s:
		if c == '0':
			seen[cur] += 1
			cur -= 1
		else:
			cur += 1
			seen[cur] += 1
	cur = START
	while True:
		if seen[cur] > 1 or (seen[cur] > 0 and seen[cur + 1] == 0):
			seen[cur] -= 1
			cur -= 1
			print('0', end='', flush=False)
		elif seen[cur + 1] > 0:
			cur += 1
			seen[cur] -= 1
			print('1', end='', flush=False)
		else:
			break
	print(flush=False)


def read_one_line_input():
	s = input()
	return int(s)

def read_lines_input(n):
	lines = []
	for i in range(n):
		s = input()
		lines.append(s)
	return lines

def print_list(out_list):
	[print(s) for s in out_list]

def main(line):
	out = ''
	length = len(line)
	if length == 1:
		return str(line)
	yi_list = [[0 for col in range(2)] for row in range(2 * length + 1)]
	yi_cur = length
	for i in range(length):
		if line[i] == '0':
			yi_list[yi_cur][0] += 1
			yi_cur -= 1
		else:
			yi_list[yi_cur][1] += 1
			yi_cur += 1
	yi_cur = length
	for i in range(length):
		if yi_list[yi_cur][0] > 0 and yi_list[yi_cur - 1][1] > 0 or yi_list[yi_cur][1] == 0:
			yi_list[yi_cur][0] -= 1
			yi_cur -= 1
			out += '0'
		else:
			yi_list[yi_cur][1] -= 1
			yi_cur += 1
			out += '1'
	return out
n = read_one_line_input()
lines = read_lines_input(n)
out_list = []
for line in lines:
	out = main(line)
	out_list.append(out)
print_list(out_list)