CF332E.Binary Key

Let's assume that p and q are strings of positive length, called the container and the key correspondingly, string q only consists of characters 0 and 1. Let's take a look at a simple algorithm that extracts message s from the given container p:

i = 0;
j = 0;
s = <>;
while i is less than the length of the string p
{
if q[j] == 1, then add to the right of string s character p[i];
increase variables i, j by one;
if the value of the variable j equals the length of the string q, then j = 0;
}

In the given pseudocode i, j are integer variables, s is a string, '=' is an assignment operator, '==' is a comparison operation, '[]' is the operation of obtaining the string character with the preset index, '<>' is an empty string. We suppose that in all strings the characters are numbered starting from zero.

We understand that implementing such algorithm is quite easy, so your task is going to be slightly different. You need to construct the lexicographically minimum key of length k, such that when it is used, the algorithm given above extracts message s from container p (otherwise find out that such key doesn't exist).

假设 $p$ 和 $q$ 是两个长度为正的字符串，分别称为容器和密钥；字符串 $q$ 仅由字符 0 和 1 组成。我们考察如下简单算法，该算法从给定容器 $p$ 中提取消息 $s$：

i = 0;  
j = 0;  
s = <>;  
while i 小于字符串 p 的长度  
{  
    如果 q[j] == 1，则将字符 p[i] 添加到字符串 s 的右侧；  
    将变量 i、j 各增加 1；  
    如果变量 j 的值等于字符串 q 的长度，则令 j = 0；   
}  

在上述伪代码中，$i$、$j$ 为整数变量，$s$ 为字符串，= 为赋值操作符，== 为比较运算符，[] 表示按给定下标获取字符串中的字符，<> 表示空字符串。我们假定所有字符串的字符下标均从 $0$ 开始编号。

我们理解实现该算法十分容易，因此你的任务略有不同：你需要构造一个字典序最小的长度为 $k$ 的密钥，使得当使用该密钥时，上述算法能从容器 $p$ 中准确提取出消息 $s$；若不存在这样的密钥，则需判定其不存在。

The first two lines of the input are non-empty strings p and s (1 ≤ |p| ≤ 106, 1 ≤ |s| ≤ 200), describing the container and the message, correspondingly. The strings can contain any characters with the ASCII codes from 32 to 126, inclusive.

The third line contains a single integer k (1 ≤ k ≤ 2000) — the key's length.

输入的前两行是非空字符串 $p$ 和 $s$（$1 \le |p| \le 10^6$，$1 \le |s| \le 200$），分别表示容器和消息。这些字符串可包含 ASCII 码在 $32$ 到 $126$（含）之间的任意字符。

第三行包含一个整数 $k$（$1 \le k \le 2000$）——密钥的长度。

Print the required key (string of length k, consisting only of characters 0 and 1). If the key doesn't exist, print the single character 0.

输出所需的密钥（长度为 $k$ 的字符串，仅由字符 0 和 1 组成）。如果该密钥不存在，则输出单个字符 0。

String x = _x_1_x_2... x__p is lexicographically smaller than string y = _y_1_y_2... y__q, if either p < q and _x_1 = _y_1, _x_2 = _y_2, ... , x__p = y__p, or there exists such integer r (0 ≤ r < min(p, q)) that _x_1 = _y_1, _x_2 = _y_2, ... , x__r = y__r and x__r + 1 < y__r + 1. Symbols are compared according to their ASCII codes.

字符串 $x = x_1x_2\ldots x_p$ 在字典序上小于字符串 $y = y_1y_2\ldots y_q$，当且仅当满足以下任一条件：

• $p < q$ 且 $x_1 = y_1,\, x_2 = y_2,\, \ldots,\, x_p = y_p$；
• 或存在某个整数 $r$（满足 $0 \le r < \min(p, q)$），使得 $x_1 = y_1,\, x_2 = y_2,\, \ldots,\, x_r = y_r$，且 $x_{r+1} < y_{r+1}$。
  字符按照其 ASCII 码进行比较。