CF1360H.Binary Median

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] \lt 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.

考虑所有长度为 $m$（$1 \le m \le 60$）的二进制字符串。二进制字符串仅由字符 0 和 1 组成。例如，0110 是一个二进制字符串，而 012aba 不是。显然，这样的字符串总共有恰好 $2^m$ 个。

字符串 $s$ 在字典序上小于字符串 $t$（两者长度均为 $m$），当且仅当在从左往右第一个它们不同的位置 $i$ 上，满足 $s[i] \lt t[i]$。这正是字典中以及大多数现代编程语言中标准字符串比较的方式。例如，字符串 01011 在字典序上小于字符串 01100，因为前两个字符相同，而在第一个字符串中第三个字符（0）小于第二个字符串中对应位置的字符（1）。

我们从该集合中移除 $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$ 表示对实数 $x$ 向下取整（即不大于 $x$ 的最大整数）。

例如，若 $n=3$，$m=3$，且 $a=[\text{010}, \text{111}, \text{001}]$，则移除这些字符串并排序后，结果为：$[\text{000}, \text{011}, \text{100}, \text{101}, \text{110}]$。因此所求中位数为 100。

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$.

第一行包含一个整数 $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$。

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.

输出 $t$ 个测试用例的答案。对每个测试用例，输出一个长度为 $m$ 的字符串——即对应测试用例中剩余字符串经排序后所得序列的中位数。

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.

第一个测试用例已在题目描述中说明。

在第二个测试用例中，移除字符串并排序后的结果为 $[001, 010, 101, 110]$。因此，所求的中位数为 010。