Рассмотрим все двоичные строки длины \(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.
Примечание
Первый набор тестовых данных примера разобран в условии.
Во втором наборе результат после удаления строк и сортировки равен \([\)001, 010, 101, 110\(]\). Следовательно, искомая медиана равна 010.