Квантовые дыры, разрушающие вселенные, иногда можно «залатать», тем самым остановив разрушение мира. Но это удается далеко не всегда.
Мигель придумал способ оценивать опасность квантовой дыры целым числом. Для этого сначала информация о квантовой дыре представляется в виде битовой строки длины ровно $$$n$$$. Каждая ее подстрока $$$t$$$ (последовательность подряд идущих бит) длины $$$k$$$ вносит свой независимый вклад $$$\mathtt{danger}(t) = d_t$$$ в суммарную опасность дыры, а именно: $$$$$$\mathtt{danger}(s) = \sum\limits_{i=1}^{n-k+1} \mathtt{danger}(s_{i,\ldots,i+k-1}) \text{,}$$$$$$ где $$$s_{i,\ldots,i+k-1}$$$ означает подстроку $$$s$$$ длины $$$k$$$ с началом в $$$i$$$-м бите.
Значения опасности всех двоичных строк длины $$$k$$$ уже изучены и известны, всего таких значений $$$2^k$$$. Например, для $$$k = 2$$$ вам известны $$$4$$$ значения: $$$d_{\mathtt{00}}$$$, $$$d_{\mathtt{01}}$$$, $$$d_{\mathtt{10}}$$$, $$$d_{\mathtt{11}}$$$.
Сегодня Марго Кесс от скуки пришла в голову идея найти описание самой безопасной квантовой дыры. Найдите битовую строку длины ровно $$$n$$$, опасность которой минимальна.
В первой строке входных данных даны два числа $$$n$$$ и $$$k$$$ — длина искомой строки и длина подстрок, соответственно ($$$1 \le n \le 1000$$$, $$$1 \le k \le 10$$$).
Во второй строке через пробел перечислены $$$2^k$$$ чисел: $$$d_\mathtt{00 \ldots 00}$$$, $$$d_\mathtt{00 \ldots 01}$$$, $$$d_\mathtt{00 \ldots 10}$$$, ..., $$$d_\mathtt{11 \ldots 10}$$$ и $$$d_\mathtt{11 \ldots 11}$$$ — уровни опасности всех возможных битовых строк длины $$$k$$$ в лексикографическом порядке ($$$1 \le d_t \le 1000$$$).
В качестве ответа выведите наименее опасную строку длины $$$n$$$. Если таких строк несколько, вы можете вывести любую из них.
7 24 2 1 3
1010101
5 38 5 4 6 3 5 6 7
01001
5 3486 750 753 40 798 644 599 56
01111
5 2358 906 7 859
10000
В первом примере опасность получившейся строки равна $$$d_\mathtt{10} + d_\mathtt{01} + d_\mathtt{10} + d_\mathtt{01} + d_\mathtt{10} + d_\mathtt{01}$$$, то есть $$$3 \cdot (d_\mathtt{10} + d_\mathtt{01}) = 3 \cdot (1 + 2) = 9$$$. Обратите внимание, что это не единственный возможный ответ с таким уровнем опасности.
Во втором примере опасность получившейся строки равна $$$d_\mathtt{010} + d_\mathtt{100} + d_\mathtt{001} = 4 + 3 + 5 = 12$$$.
В четвертом примере опасность получившейся строки равна $$$c_{10} + 3 \cdot c_{00} = 1081$$$.