H. Двоичная медиана
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим все двоичные строки длины $$$m$$$ ($$$1 \le m \le 60$$$), то есть строки, состоящие из символов 0 и 1. Например, 0110 является двоичной строкой, а 012aba — нет. Очевидно, что всего таких строк ровно $$$2^m$$$.

Строка $$$s$$$ лексикографически меньше строки $$$t$$$ (обе имеют одинаковую длину $$$m$$$), если в первой слева позиции $$$i$$$, в которой они отличаются, верно $$$s[i] < t[i]$$$. Именно такой способ сравнения строк используется в словарях и в большинстве современных языков программирования при их сравнении стандартным способом. Например, строка 01011 лексикографически меньше строки 01100, потому что первые два символа совпадают, а третий символ в первой строке меньше, чем во второй.

Удалим из этого множества $$$n$$$ ($$$1 \le n \le \min(2^m-1, 100)$$$) различных двоичных строк $$$a_1, a_2, \ldots, a_n$$$, каждая длины $$$m$$$. Таким образом, в множестве останется $$$k=2^m-n$$$ строк. Отсортируем все строки полученного множества в порядке лексикографического возрастания (как в словаре).

Пронумеруем все строки после сортировки от $$$0$$$ до $$$k-1$$$. Выведите строку, номер которой равен $$$\lfloor \frac{k-1}{2} \rfloor$$$ (такой элемент называется медианой), где $$$\lfloor x \rfloor$$$ является округлением числа вниз к ближайшему целому.

Например, если $$$n=3$$$, $$$m=3$$$ и $$$a=[$$$010, 111, 001$$$]$$$, то после удаления строк $$$a_i$$$ и сортировки результат примет вид: $$$[$$$000, 011, 100, 101, 110$$$]$$$. Таким образом, искомая медиана равна 100.

Входные данные

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов тестовых данных в тесте. Далее следуют $$$t$$$ наборов тестовых данных.

В первой строке каждого набора записаны целые числа $$$n$$$ ($$$1 \le n \le \min(2^m-1, 100)$$$) и $$$m$$$ ($$$1 \le m \le 60$$$), где $$$n$$$ — количество удаляемых строк, $$$m$$$ — длина двоичных строк. Следующие $$$n$$$ строк содержат $$$a_1, a_2, \ldots, a_n$$$ — различные двоичные строки длины $$$m$$$.

Суммарная длина всех заданных двоичных строк во всех наборах тестовых данных в одном тесте не превосходит $$$10^5$$$.

Выходные данные

Выведите $$$t$$$ ответов на наборы тестовых данных. Ответом является строка длины $$$m$$$ — медиана оставшихся строк.

Пример
Входные данные
5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10
Выходные данные
100
010
0
1
11
Примечание

Первый набор тестовых данных примера разобран в условии.

Во втором наборе результат после удаления строк и сортировки равен $$$[$$$001, 010, 101, 110$$$]$$$. Следовательно, искомая медиана равна 010.