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

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

Парламент Варении состоит из нескольких палат, пронумерованных натуральными числами от 1 до \(10^9\) (палаты с некоторыми номерами могут отсутствовать). Принятие законов происходит следующим образом: сначала каждый депутат голосует за или против принимаемого закона, затем считается число \(K\) — количество палат парламента, в которых голосование признано действительным (голосование может быть признано недействительным в том и только том случае, если количество проголосовавших «за» равно количеству проголосовавших «против»). Далее, чтобы принять итоговое решение о принятии закона, применяется новейшая электронная система: она случайным образом выбирает числа \(A\) и \(B\), а затем сравнивает \(A\)/\(K\) и \(B\).

В очередной раз парламенту Варении предстоит решить судьбу нового закона, предложенного премьер-министром. Однако политические взгляды различных ветвей власти Варении практически противоположны, поэтому все депутаты считают принятие этого закона неприемлемым. Но по своему опыту депутаты знают, что даже если они все проголосуют против, система (не без помощи премьер-министра) может подобрать числа \(A\) и \(B\) таким образом, чтобы закон всё равно оказался принят. Поэтому единственный способ отложить принятие нежелательного закона — это вызвать сбой в системе. Для этого достаточно, чтобы во всех палатах был достигнут ничейный результат голосования: тогда K будет равно нулю, система попытается разделить на ноль, и ещё целый месяц лучшие программисты Варении будут восстанавливать работу электронной системы голосования.

Однако может так получиться, что в одной из палат число депутатов нечётно, поэтому ничья в данной палате невозможна. На этот случай депутаты недавно приняли закон, по которому спикер парламента (не принадлежащий ни одной из палат) может отдать свой голос одной из палат. Поэтому вызвать сбой в системе всегда возможно, если существует не более одной палаты с нечётным количеством депутатов.

По информации о составе палат найдите палату, которой спикер должен отдать свой голос (если это необходимо).

Енот Вася — начинающий художник. Недавно он приобрёл подержанную кисточку (как рассказал продавец, она сделана из хвоста самого Малевича!), достал холст и решил произвести на свет свой первый шедевр.

Как оказалось, лет кисточке немало, потому она способна лишь ставить кляксы в форме пяти квадратиков, расположенных крестиком (координаты их центров будут равны (\(x\), \(y\)), (\(x\)−1, \(y\)), (\(x\), \(y\)−1), (\(x\)+1, \(y\)), (\(x\), \(y\)+1)). Вася поставил \(N\) клякс, разочаровался в идее первого шедевра и задумался о месте для нового. Но ведь если он закрасил весь холст, писать будет негде...

Выясните, закрасил ли своими действиями Вася весь холст.

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

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

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

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

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

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

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

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