E. Двоичный ключ
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть p и q — строки положительной длины, называемые контейнером и ключом соответственно, причём строка q состоит лишь из символов 0 и 1. Рассмотрим несложный алгоритм, выделяющий сообщение s из заданного контейнера p:


i = 0;
j = 0;
s = <>;
пока i меньше длины строки p
{
если q[j] == 1, то приписать справа к строке s символ p[i];
увеличить переменные i, j на единицу;
если значение переменной j равно длине строки q, то j = 0;
}

В приведенном псевдокоде i, j — целочисленные переменные, s — строка, '=' — оператор присваивания, '==' — операция сравнения, '[]' — операция получения символа строки с заданным индексом, '<>' — пустая строка. Предполагается, что нумерация символов во всех строках начинается с нуля.

Понятно, что реализовать данный алгоритм довольно легко, а потому перед Вами будет стоять несколько другая задача. Необходимо построить минимальный лексикографически ключ длины k, при использовании которого приведенный выше алгоритм выделит из контейнера p сообщение s (или выяснить, что такого ключа не существует).

Входные данные

Первые две строки входных данных — непустые строки p и s (1 ≤ |p| ≤ 106, 1 ≤ |s| ≤ 200), задающие контейнер и сообщение соответственно. Строки могут содержать любые символы с ASCII-кодами от 32 до 126 включительно.

Третья строка содержит единственное целое число k (1 ≤ k ≤ 2000) — длину ключа.

Выходные данные

Выведите искомый ключ (строку длины k, состоящую только из символов 0 и 1). Если ключа не существует, выведите единственный символ 0.

Примеры
Входные данные
abacaba
aba
6
Выходные данные
100001
Входные данные
abacaba
aba
3
Выходные данные
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-кодам.