Про строку известно, что некоторые её подстроки равны между собой. Восстановите исходную строку.

Иван-царевич в глубокой печали: морской царь поручил ему перепахать до утра огромную пустошь на морском дне и засеять рожью. Понятно, что без волшебства тут не справиться! По счастью, дочь морского царя, Василиса Премудрая, предложила Ивану-царевичу свою помощь.

У Василисы в сундуке хранятся грамоты с древними заклинаниями. Она втайне была в учении у самой Бабы-Яги, поэтому знает, что, чтобы творить волшебство, нужно произнести заклинание, да такое, в котором скрыто содержится нужное волшебное слово. Но достаточно ли сильны заклинания, хранящиеся в сундуке?

Вот что Василиса Премудрая узнала от Бабы-Яги:

Вхождение слова в заклинание — это подпоследовательность букв заклинания, совпадающая со словом. Буквы слова могут идти не подряд, но должны быть расположены в том же порядке. К примеру, заклинания «cadabra» и «barabara» содержат слово «abra», а заклинание «raba» — не содержит.

Вхождение называют скрытым, если никакие две его буквы не идут подряд. Например, в заклинание «abuba» слово «aua» входит скрыто, так как буквы вхождения (первая, третья и пятая) идут не подряд, а через одну. В заклинание «bauab» слово «aua», напротив, входит не скрыто.

Силой заклинания относительно волшебного слова считается количество скрытых вхождений в него этого волшебного слова. Например, волшебное слово «az» в заклинание «abazaba» входит два раза, но только один раз — скрыто, поэтому сила его равна единице.

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

Зная заклинание и волшебное слово, посчитайте силу этого заклинания относительно данного волшебного слова.

Миша уже научился хорошо фотографировать и недавно увлекся программированием. Первая программа, которую он написал, позволяет формировать негатив чёрно-белого изображения.

Бинарное чёрно-белое изображение — это прямоугольник, состоящий из пикселей, каждый из которых может быть либо чёрным, либо белым. Негатив такого изображения получается путём замены каждого чёрного пикселя на белый, а каждого белого пикселя — на чёрный.

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

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

Требуется написать программу, которая в качестве входных данных использует исходное бинарное чёрно-белое изображение и полученный Мишиной программой негатив, и на основе этого определяет количество пикселей, в которых допущена ошибка.

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

Небольшая компания «Домострой» также решила выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов. Блок представляет собой параллелепипед размером \(1\times1\times L\), на одной из сторон которого есть место для рекламы — пространство размера \(1\times L\), в которое можно вписать ровно \(L\) букв латинского алфавита.

К сожалению, иногда сделки у компании срывались, и заранее подготовленные блоки с рекламой отправлялись на склад. Со временем там скопилось приличное количество блоков различных типов (блоки разных типов отличаются друг от друга только надписью), поэтому было решено использовать их вторично.

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

После того, как некоторое число \(K\) блоков, каждый из которых имеет длину \(L\), поставили друг на друга, получилась прямоугольная таблица размером \(K\times L\), в каждой клетке которой находится буква латинского алфавита. Каждый рекламный блок соответствует строке этой таблицы. Теперь содержимое этой таблицы выписывается по столбцам, начиная с самого левого. При этом в каждом столбце буквы выписываются сверху вниз. В случае, изображённом на рисунке, в результате этого процесса получилась бы строка «TOEIIZENITKN». Необходимо, чтобы рекламная надпись, требуемая заказчику, входила в получившуюся строку как подстрока «TOEIIZENITKN».

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