假设p和q是正长度的字符串,分别称为容器和密钥,字符串q仅由字符0和1组成。让我们看一个从给定容器p中提取消息s的简单算法:
给定的伪代码中,i、j 为整型变量,s 为字符串,'=' 为赋值运算符,'==' 为比较操作,'[]' 为获取预设索引的字符串字符操作,'<>' 为空字符串。我们假设所有字符串中的字符都是从零开始编号的。
我们知道实现这种算法非常容易,因此您的任务会略有不同。您需要构造长度为 k 的字典顺序最小密钥,以便在使用它时,上面给出的算法从容器 p 中提取消息 s (否则会发现这样的密钥不存在)。
输入
输入的前两行是非空字符串 p 和 s (1 ≤ |p| ≤ 106, 1 ≤ |s| ≤ 200),分别描述容器和消息。字符串可以包含 ASCII 代码从 32 到 126(含 32 和 126)的任何字符。
第三行包含一个整数 k (1 ≤ k ≤ 2000) — 密钥的长度。
输出
打印所需的密钥(长度为 k 的字符串,仅由字符 0 和 1 组成)。如果键不存在,则打印单个字符 0。
示例
输入 #1
abacaba aba 6
输出 #1
100001
输入 #2
abacaba aba 3
输出 #2
0
注意
字符串 x = x1x2... xp 按字典顺序小于字符串 y = y1y2... yq,如果 p < q 且 x1 = y1, x2 = y2, ... , xp = yp,或者存在这样的整数 r (0 ≤ r < min(p, q)) 使得 x1 = y1, x2 = y2, ... , xr = yr 并且xr + 1 < yr + 1。根据 ASCII 代码对符号进行比较。