Consider all binary strings of length $m$ ($1 \le m \le 60$). A binary string is a string that consists of the characters 0 and 1 only. For example, 0110 is a binary string, and 012aba is not. Obviously, there are exactly $2^m$ such strings in total.

The string $s$ is lexicographically smaller than the string $t$ (both have the same length $m$) if in the first position $i$ from the left in which they differ, we have $s[i] < t[i]$. This is exactly the way strings are compared in dictionaries and in most modern programming languages when comparing them in a standard way. For example, the string 01011 is lexicographically smaller than the string 01100, because the first two characters are the same, and the third character in the first string is less than that in the second.

We remove from this set $n$ ($1 \le n \le \min(2^m-1, 100)$) distinct binary strings $a_1, a_2, \ldots, a_n$, each of length $m$. Thus, the set will have $k=2^m-n$ strings. Sort all strings of the resulting set in lexicographical ascending order (as in the dictionary).

We number all the strings after sorting from $0$ to $k-1$. Print the string whose index is $\lfloor \frac{k-1}{2} \rfloor$ (such an element is called median), where $\lfloor x \rfloor$ is the rounding of the number down to the nearest integer.

For example, if $n=3$, $m=3$ and $a=[$010, 111, 001$]$, then after removing the strings $a_i$ and sorting, the result will take the form: $[$000, 011, 100, 101, 110$]$. Thus, the desired median is 100.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then, $t$ test cases follow.

The first line of each test case contains integers $n$ ($1 \le n \le \min(2^m-1, 100)$) and $m$ ($1 \le m \le 60$), where $n$ is the number of strings to remove, and $m$ is the length of binary strings. The next $n$ lines contain $a_1, a_2, \ldots, a_n$ — distinct binary strings of length $m$.

The total length of all given binary strings in all test cases in one test does not exceed $10^5$.


-----Output-----

Print $t$ answers to the test cases. For each test case, print a string of length $m$ — the median of the sorted sequence of remaining strings in the corresponding test case.


-----Example-----
Input
5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10

Output
100
010
0
1
11



-----Note-----

The first test case is explained in the statement.

In the second test case, the result after removing strings and sorting is $[$001, 010, 101, 110$]$. Therefore, the desired median is 010.

Difficulty: introductory

Starter code:

Solutions:
def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


t = read_int()
for case_num in range(t):
    n, m = read_ints()
    a = []
    for i in range(n):
        a.append(int(input(), 2))
    a.sort()
    k = 2 ** m - n
    ans = (k - 1) // 2
    for ai in a:
        if ai <= ans:
            ans += 1
    binary = '{:b}'.format(ans)
    print(binary.rjust(m, '0'))


def count_smaller(value, banlist):
    total = value
    for v in banlist:
        if v < value:
            total -= 1
    return total

cases = int(input())
for case in range(cases):
    n, m = map(int, input().split())
    banned = []
    for i in range(n):
        banned.append(int(input(), 2))
    desindex = ((1 << m) - n - 1) // 2
    candid = desindex
    while (count_smaller(candid, banned) < desindex) or (candid in banned):
        candid += 1
    print(bin(candid)[2:].zfill(m))

import bisect


for _ in range(int(input())):
    n,m=list(map(int,input().split()))
    ban=[]
    for i in range(n):
        a=input()
        ban.append(int(a,2))
    ban.sort()
    k=2**m-n
    start=0
    end=2**m
    def func(num):
        res=num
        index=bisect.bisect_left(ban,num)
        res-=index
        return res
    while end-start>1:
        test=(end+start)//2
        if (k-1)//2>=func(test):
            start=test
        else:
            end=test
    if (k-1)//2>=func(end):
        ans=end
    else:
        ans=start
    ban=set(ban)
    while ans in ban:
        ans-=1
    res=bin(ans)[2:]
    res="0"*(m-len(res))+res
    print(res)
    





from bisect import bisect_left
for _ in range(int(input())):
    n, m = map(int, input().split())
    A = []
    G = set()
    for __ in range(n):
        kek = int(input(), 2)
        A.append(kek)
        G.add(kek)
    A.sort()
    k = 2**m - n
    k = (k - 1) // 2
    ans = -1
    for num in range(2**(m-1)-2*n-20, 2**(m-1)+2*n+20):
        if 0<=num<2**m:
            lol = num - bisect_left(A, num+1)
            if lol == k and num not in G:
                ans = num
                break
    l = ans
    print(str(bin(l))[2:].zfill(m))

def solve(mid):
    small = mid
    large = 2 ** m - mid - 1
    for val in s:
        if val < mid:
            small -= 1
        if val > mid:
            large -= 1
    return small < large

def solve2(mid):
    small = mid
    large = 2 ** m - mid - 1
    for val in s:
        if val < mid:
            small -= 1
        if val > mid:
            large -= 1
    return small <= large


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    s = set([int(input(), 2) for i in range(n)])
    ng = -1
    ok = 2 ** m + 2
    if len(s) % 2 == 0:
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if mid in s:
                for i in range(ng + 1, ok):
                    if i not in s:
                        mid = i
                        break
            if solve(mid):
                ng = mid
            else:
                ok = mid
        print('{:060b}'.format(ng)[::-1][0:m][::-1])
    else:
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if mid in s:
                for i in range(ng + 1, ok):
                    if i not in s:
                        mid = i
                        break
            if solve2(mid):
                ng = mid
            else:
                ok = mid
        print('{:060b}'.format(ng)[::-1][0:m][::-1])

def check(x,nums,k):
    small = x+1
    for i in nums:
        if i <= x:
            small -= 1

    if small <= (k-1)//2:
        return False

    return True

def solve(nums,m,ans):
    n = len(nums)
    low = 0
    high = pow(2,m)-1
    x = 0
    k = pow(2,m)-n
    while low <= high:
        mid = (low+high)//2
        if check(mid,nums,k):
            x = mid
            high = mid-1
        else:
            low = mid+1

    x = bin(x)[2:]
    if len(x) < m:
        x = '0'*(m-len(x))+x

    ans.append(x)
    

def main():
    t = int(input())
    ans = []
    for i in range(t):
        n,m = list(map(int,input().split()))
        nums = set()
        for j in range(n):
            x = int(input(),2)
            nums.add(x)

        solve(nums,m,ans)

    for i in ans:
        print(i)


main()



import bisect
T = int(input())

for _ in range(T):
    N, M = list(map(int, input().split()))
    aa = sorted([int(input(), 2) for _ in range(N)])

    K = 1 << M

    ans = 0

    for k in reversed(list(range(M))):
        tmp = ans + (1 << k)
        La = bisect.bisect_left(aa, tmp)
        Ra = N - La

        L = tmp - La
        R = (K - tmp) - Ra

        if L < R:
            ans = tmp
        else:
            continue

    print(f"{ans:0{M}b}")


import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n,m=list(map(int,input().split()))
    A=sorted([int(input().strip(),2) for i in range(n)])
    A+=[1<<63]

    ind=(2**m-n-1)//2

    indskip=0
    ANS=0

    #print(A)

    while True:
        #print(ANS,ind,indskip)
        if A[indskip]==ANS:
            ANS+=1
            indskip+=1
            continue
        if A[indskip]-ANS<=ind:
            ind-=A[indskip]-ANS
            ANS=A[indskip]+1
            indskip+=1
        else:
            ANS+=ind
            break

    print(bin(ANS)[2:].zfill(m))

        
        

    
                    
                

    
                
    


T = int(input())


def move_up(taken, s):
    s += 1
    while s in taken:
        s += 1
    return s


def move_down(taken, s):
    s -= 1
    while s in taken:
        s -= 1
    return s

for t in range(T):
    N, M = [int(_) for _ in input().split()]
    start = (1 << (M-1))-1
    taken = set()
    rd = True
    for i in range(N):
        el = int(input(), 2)
        taken.add(el)
        if el > start:
            if not rd:
                start = move_down(taken, start)
        elif el < start:
            if rd:
                start = move_up(taken, start)
        else:
            if rd:
                start = move_up(taken, start)
            else:
                start = move_down(taken, start)
        rd = not rd

    print(format(start, '0{}b'.format(M)))


import sys

t = int(sys.stdin.readline().strip())
for _ in range(t):
	n, m = list(map(int, sys.stdin.readline().strip().split()))
	s = set()
	mid = 2**(m-1)-1


	flag = 0
	for i in range(n):
		x = int(sys.stdin.readline().strip(), 2)
		s.add(x)

		if x > mid and flag == 0:
			flag = 1
		elif x > mid and flag == 1:
			flag = 0
			mid -= 1
			while mid in s:
				mid -= 1

		elif x < mid and flag == 0:
			flag = 1
			mid += 1
			while mid in s:
				mid += 1
		elif x < mid and flag == 1:
			flag = 0

		else:
			if flag == 1:
				flag = 0
				mid -= 1
				while mid in s:
					mid -= 1
			else:
				flag = 1
				mid += 1
				while mid in s:
					mid += 1
	ans = bin(mid)[2:]
	ans = '0'*(m-len(ans)) + ans
	print(ans)





	




def main():
    for t in range(int(input())):
        n, m = map(int, input().split())
        l = []
        for i in range(n):
            l.append((int(input(), 2)))
            
        l.sort()
        median = (2 ** m - n - 1) // 2
        # print(l)
        # print(median)
        for i in l:
            if i <= median:
                median += 1
            # print(median)
        while median in l:
            median += 1
        
        ans = bin(median)[2:]
        temp = ''
        for i in range(len(ans), m):
            temp += '0'
        print(temp + ans)
                            
        
main()

import sys
# sys.setrecursionlimit(10**6) 
input=sys.stdin.readline
t=int(input())
import math
for t1 in range(t):
    # n=int(input())
    k,n=list(map(int,input().split(" ")))
    l=[]
    for i in range(k):
        s=input()
        s=s.strip()
        l.append(int(s,2))
    l.sort()
    a=0
    curr="0"+"1"*(n-1)
    curr=int(curr,2)
    temp=1<<n
    d={}
    for i in range(k):
        d[l[i]]=1
        if(temp%2==0):
            if(l[i]>curr):
                a=1
            else:
                
                while(d.get(curr+1,0)==1):
                    curr+=1
                curr+=1
                #increase by 1
        else:
            if(l[i]>=curr):
                while(d.get(curr-1,0)==1):
                    curr-=1
                #decrease by 1
                curr-=1
            else:
                a=1
        temp-=1
    z=bin(curr)[2:]
    if(len(z)<n):
        diff=n-len(z)
        z="0"*diff+z
    print(z)




import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n,m=map(int,input().split())
    A=sorted([int(input().strip(),2) for i in range(n)])
    A+=[1<<63]

    ind=(2**m-n-1)//2

    indskip=0
    ANS=0

    #print(A)

    while True:
        #print(ANS,ind,indskip)
        if A[indskip]==ANS:
            ANS+=1
            indskip+=1
            continue
        if A[indskip]-ANS<=ind:
            ind-=A[indskip]-ANS
            ANS=A[indskip]+1
            indskip+=1
        else:
            ANS+=ind
            break
    #print(ANS,ind)
    print(bin(ANS)[2:].zfill(m))

import math
t=int(input())
def convert(s): 
  
    # initialization of string to "" 
    new = "" 
  
    # traverse in the string  
    for x in s: 
        new += x  
  
    # return string  
    return new 
      
for i in range(t):
    a,b=list(map(int,input().split()))
    removed=[]
    for j in range(a):
        removed.append(int(input(), 2))
    removed.sort()
    pointer=0
    leftcount=0
    for j in range(2**(b-1)-101,2**(b-1)+101):
        if pointer<a:
            while removed[pointer]<j:
                pointer+=1
                leftcount+=1
                if pointer==a:
                    break
        if j+1-leftcount>=2**b-j-1-(a-leftcount):
            if j in removed:
                continue
            s="{0:b}".format(j)
            ans=[]
            for k in range(b-len(s)):
                ans.append('0')
            for k in range(len(s)):
                ans.append(s[k])
            print(convert(ans))
            break


import sys
input = sys.stdin.readline
def stringminus(s):
    i=-1
    n=len(s)
    s2=["0"]*n
    for j in range(n):
        s2[j]=s[j]
    while s[i]=="0":
        s2[i]="1"
        i-=1
    s2[i]="0"
    sol=s2[0]
    for i in range(1,n):
        sol+=s2[i]
    return sol
def stringplus(s):
    i=-1
    n=len(s)
    s2=["0"]*n
    for j in range(n):
        s2[j]=s[j]
    while s[i]=="1":
        s2[i]="0"
        i-=1
    s2[i]="1"
    sol=s2[0]
    for i in range(1,n):
        sol+=s2[i]
    return sol
for f in range(int(input())):
    rem=set()
    med="0"
    isc=0
    n,m=map(int,input().split())
    for i in range(m-1):
        med+="1"
    for i in range(n):
        s=input()
        s=s[0:m]
        if s>med:
            isc+=1
        if s<med:
            isc-=1
        if s==med:
            if isc==0:
                isc=-1
            else:
                isc=2
        rem.add(s)
        if isc==-1:
            med=stringplus(med)
            while med in rem:
                med=stringplus(med)
            isc=1
        if isc==2:
            med=stringminus(med)
            while med in rem:
                med=stringminus(med)
            isc=0
    print(med)

import sys

inp = [x for x in sys.stdin.read().split()]; ii = 0

ttt = int(inp[ii]); ii += 1
res = []
for _ in range(ttt):
	n, m = int(inp[ii]), int(inp[ii + 1]); ii += 2
	a = []
	for _ in range(n):
		temp = inp[ii]; ii += 1
		x = 0
		for i in range(m):
			if temp[i] == '1':
				x += 1 << m - 1 - i
		a.append(x)
	t = ((1 << m) - n - 1) // 2
	low, high = 0, 1 << m
	while high - low > 1:
		mid = low + high >> 1
		if mid - sum([x < mid for x in a]) <= t:
			low = mid
		else:
			high = mid
	res.append("".join(str(int(not not low & 1 << i)) for i in range(m - 1, -1, -1)))
print("\n".join(str(x) for x in res))

t = int(input())
for y in range(t):
	n,m = map(int,input().split())
	mid = 2**(m-1)-1
	d = dict()
	for i in range(n):
		x = int(input(),2)
		d[x] = 1
		if(i%2 == 0):
			if(x <= mid):
				mid += 1
				while(mid in d):
					mid += 1
		else:
			if(x >= mid):
				mid -= 1
				while(mid in d):
					mid -= 1
	t = ""
	for i in range(m-1,-1,-1):
		x = 2**i
		if(mid&x):
			t += '1'
		else:
			t += '0'
	print(t)