human
Consider all binary strings of length m (1 ≤ m ≤ 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 ≤ n ≤ min(2^m-1, 100)) distinct binary strings a_1, a_2, …, 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 ⌊ (k-1)/(2) ⌋ (such an element is called median), where ⌊ x ⌋ 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 ≤ t ≤ 1000) — the number of test cases. Then, t test cases follow.

The first line of each test case contains integers n (1 ≤ n ≤ min(2^m-1, 100)) and m (1 ≤ m ≤ 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, …, 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...
Using python3 can you solve the prior task?
assistant
#Here is Python program to print the string whose index is ⌊ (k-1)/(2) ⌋ (such an element is called median), where ⌊ x ⌋ is the rounding of the number down to the nearest integer.

""" Python 3 compatibility tools. """
from __future__ import division, print_function
import itertools
import sys
import os
from io import BytesIO, IOBase
 
 
if sys.version_info[0] < 3:
  input = raw_input
  range = xrange
 
  filter = itertools.ifilter
  map = itertools.imap
  zip = itertools.izip
 
 
def is_it_local():
  script_dir = str(os.getcwd()).split('/')
  username = "dipta007"
  return username in script_dir
 
 
def READ(fileName):
  if is_it_local():
    sys.stdin = open(f'./{fileName}', 'r')
 
# region fastio
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")
 
if not is_it_local():
  sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
  input = lambda:...