量子洞

• 时间限制：1 秒
• 内存限制：256 MB
• 输入：标准输入
• 输出：标准输出

题目描述

量子洞会摧毁宇宙，有时可以被“修补”，从而阻止世界毁灭。但这并不总是成功。

米格尔想出了一个用整数评估量子洞危险度的方法。为此，首先将量子洞的信息表示为长度为 $n$ 的比特串。它的每个长度为 $k$ 的子串 $t$（连续比特序列）都会对总危险度产生一个独立的贡献 $\mathtt{danger}(t) = d_t$，即： $$ \mathtt{danger}(s) = \sum_{i=1}^{n-k+1} \mathtt{danger}(s_{i,\ldots,i+k-1}), $$ 其中 $s_{i,\ldots,i+k-1}$ 表示从第 $i$ 个比特开始的长度为 $k$ 的子串。

所有长度为 $k$ 的二进制串的危险值已经研究清楚并已知，共有 $2^k$ 个这样的值。例如，对于 $k=2$，你知道 $4$ 个值：$d_{00}$、$d_{01}$、$d_{10}$、$d_{11}$。

今天，玛戈·凯斯无聊时突然想到要找到最安全的量子洞的描述。请找出长度为 $n$ 且危险度最小的比特串。

输入数据

第一行包含两个整数 $n$ 和 $k$ —— 所求字符串的长度和子串的长度（$1 \le n \le 1000$，$1 \le k \le 10$）。

第二行包含 $2^k$ 个以空格分隔的整数：$d_{00\ldots00}$、$d_{00\ldots01}$、$d_{00\ldots10}$、……、$d_{11\ldots10}$、$d_{11\ldots11}$ —— 所有可能的长度为 $k$ 的比特串的危险度，按字典序给出（$1 \le d_t \le 1000$）。

输出数据

输出一个长度为 $n$ 的危险度最小的比特串。如果有多个，输出任意一个。

示例

示例 1：

输入：

7 2
4 2 1 3

输出：

1010101

示例 2：

输入：

5 3
8 5 4 6 3 5 6 7

输出：

01001

示例 3：

输入：

5 3
486 750 753 40 798 644 599 56

输出：

01111

示例 4：

输入：

5 2
358 906 7 859

输出：

10000

注释

在第一个示例中，所得字符串的危险度为 $d_{10}+d_{01}+d_{10}+d_{01}+d_{10}+d_{01}$，即 $3\cdot(d_{10}+d_{01})=3\cdot(1+2)=9$。注意，这不是唯一具有该危险度的答案。

在第二个示例中，所得字符串的危险度为 $d_{010}+d_{100}+d_{001}=4+3+5=12$。

在第四个示例中，所得字符串的危险度为 $c_{10}+3\cdot c_{00}=1081$。