CF332E Binary Key

假设 $p$ 和 $q$ 是两个正长度的字符串，分别称为“容器”和“密钥”，字符串 $q$ 只包含字符 0 和 1。我们来看看一个简单的算法，它从给定的容器 $p$ 中提取消息 $s$： ``` i = 0; j = 0; s = 空字符串; while i 小于字符串 p 的长度 { 如果 q[j] == 1，则把字符 p[i] 添加到字符串 s 的右端； 变量 i、j 都加一； 如果变量 j 的值等于字符串 q 的长度，则令 j = 0； } ``` 在给出的伪代码中，$i$、$j$ 是整数变量，$s$ 是字符串，'=' 是赋值操作符，'==' 是比较操作符，'[]' 表示获取字符串第 preset 个下标的字符，空字符串记为 。我们假定所有字符串的字符编号均从 0 开始。 我们明白实现此类算法并不难，因此你的任务稍有不同。你需要构造长度为 $k$ 的按字典序最小的密钥（只包含字符 0 和 1），使得用该密钥按照上述算法从容器 $p$ 中能提取出消息 $s$（否则输出不能构造的结论）。

前两行输入为非空字符串 $p$ 和 $s$（$1 \le |p| \le 10^{6}$，$1 \le |s| \le 200$），分别表示“容器”和“消息”。字符串可以包含 ASCII 码从 32 到 126（含）范围内的任意字符。 第三行为单个整数 $k$（$1 \le k \le 2000$），表示密钥的长度。

输出所需的密钥（长度为 $k$，只包含字符 0 和 1）。如果不存在这样的密钥，输出单个字符 0。

设字符串 $x = x_{1}x_{2}\cdots x_{p}$，字符串 $y = y_{1}y_{2}\cdots y_{q}$，如果满足以下两个条件之一，则 $x$ 按字典序小于 $y$： - 要么 $p < q$ 且 $x_{1}=y_{1},x_{2}=y_{2},...,x_{p}=y_{p}$； - 要么存在整数 $r$（$0 \leq r < \min(p, q)$）使得 $x_{1}=y_{1},x_{2}=y_{2},...,x_{r}=y_{r}$ 并且 $x_{r+1}