Задача N. Циклические сдвиги ≡

Условие

Рассмотрим строку S, выступающую в качестве ключа в некотором симметричном алгоритме шифрования.

Для того, чтобы закодировать очередной символ входной последовательности, его необходимо переместить в начало такой строки путем ее циклического сдвига. Стоимость каждого отдельного сдвига определяется числом пропущенных позиций.

Требуется определить набор циклических сдвигов строки S с наименьшей общей стоимостью, необходимых для того, чтобы последовательно закодировать заданный набор символов T.

Формат входного файла

В начале входного файла "input.txt" записана строка S. Далее следует последовательность символов T, которую необходимо закодировать.

Формат выходного файла

Выходной файл "output.txt" должен содержать последовательность сдвигов строки S, оптимальным образом кодирующих строку T.
При этом сдвиги вправо обозначаются положительными числами, влево — отрицательными.

Ограничения

Полагается, что обе строки состоят из цифр и строчных букв латинского алфавита.
При этом строка T не может содержать символы, отсутствующие в строке S.

0 < |S| ≤ 500, 0 < |T| ≤ 1000

Примеры тестов

abc123ababab12abc12abxyz
ycxaa3z

2
-4
5
-3
0
-5
6

a5210zcba4210ycba3210xcb
aa42acx

0
-8
-1
7
2
2
1