«Когда мы делимся своими переживаниями, тревоги ослабевают. Половина печали рассказчика передаётся собеседнику, а другая половина вместе со звуковыми волнами возвращается миру. Так тревоги, переходя от человека к человеку, становятся всё слабее, пока не развеются по ветру».

В небольшом кругу 小 I есть $n$ человек. У человека с номером $i$ ($1 \le i \le n$) изначально есть положительное целое количество тревог $a_i$.

Чтобы уменьшить тревоги всех участников, 小 I организовал встречу для общения. На встрече все $n$ человек сидят в ряд слева направо в порядке возрастания номеров.

Время ограничено, поэтому 小 I может организовать не более $k$ бесед. Во время каждой беседы некоторый человек $p$ ($1 \le p \le n-1$) делится переживаниями с человеком $p+1$, сидящим справа от него. Сначала это приводит к $a_{p+1} \leftarrow a_{p+1}+\frac12 a_p$, а затем к $a_p \leftarrow 0$, где $\leftarrow$ означает присваивание. Для каждой беседы 小 I может произвольно выбирать рассказчика. Обратите внимание, что человек с номером $n$ не делится переживаниями с другими.

小 I хочет, чтобы у всех было как можно меньше тревог, поэтому ему интересно, каково минимально возможное значение максимального итогового количества тревог среди всех людей после встречи.

Вам нужно вывести точное значение ответа. В частности, ответ всегда можно записать в виде $\frac{S}{2^n}$, где $S$ — положительное целое число, не превосходящее $2^n\times(\max_{i=1}^n a_i)$. Вам нужно вывести двоичную запись $S$.

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

Данные считываются из файла confide.in.

В задаче несколько наборов входных данных. Первая строка содержит целое число $T$ — количество наборов. Далее последовательно описываются все наборы.

Для каждого набора первая строка содержит два целых числа $n,k$ — количество людей и максимально допустимое число бесед соответственно. Вторая строка содержит $n$ положительных целых чисел $a_1,a_2,\ldots,a_n$, описывающих исходное количество тревог каждого человека.

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

Выведите результат в файл confide.out.

Для каждого набора выведите в отдельной строке строку из символов 0 и 1, представляющую двоичную запись $S$ от старшего разряда к младшему. В выводе не должно быть ведущих нулей.

Примеры

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

3
3 1
5 2 1
3 2
5 2 1
3 3
5 2 1

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

100100
10100
10100

Примечание

Для первого набора оптимально, чтобы переживаниями поделился первый человек. Итоговые количества тревог равны $(0,4.5,1)$, поэтому выводится двоичная запись числа $4.5\times2^3=36$, то есть 100100.

Для второго и третьего наборов оптимально сначала дать высказаться второму человеку, а затем первому. Итоговые количества тревог равны $(0,2.5,2)$, поэтому выводится двоичная запись числа $2.5\times2^3=20$, то есть 10100.

Пример 2

См. файлы confide/confide2.in и confide/confide2.ans в каталоге участника.

Примечание

Ответы для семи наборов этого примера равны соответственно $10,10,8,5,3.5,2.75,2.5$.

Подзадачи

Пусть $\sum n$ обозначает сумму $n$ по всем наборам входных данных в одном тесте. Для всех наборов гарантируется:

• $1\le T\le2\times10^4$;
• $1\le n,\sum n\le2\times10^4$, $1\le k\le10^9$;
• для всех $1\le i\le n$ выполнено $1\le a_i\le10^6$.