Рассмотрим две строки \(α\) и \(β\). Их конкатенацией называется строка, получающаяся в результате приписывания к строке \(α\) строки \(β\). Эта строка обозначается \(αβ\). Например, конкатенацией строк `ab' и `ac' будет строка `abac'. Очевидно, что это определение естественным образом распространяется на конкатенацию произвольного количества строк. Так, конкатенацией нуля строк будет пустая строка, а конкатенацией одной строки будет она сама.

Рассмотрим некоторое множество \(W\), состоящее из строк. Назовём его замыканием множество \(W\)*, состоящее из тех и только тех строк, которые можно получить в результате конкатенации нуля и более строк из множества \(W\). Таким образом, множество \(W\)* содержит пустую строку, и если строка α принадлежит множеству \(W\)*, а строка \(β\) принадлежит множеству \(W\), то строка \(αβ\) принадлежит множеству \(W\)*. Более того, все элементы множества \(W\)* можно представить в таком виде, то есть \(W\)* является пересечением всех множеств с указанными выше свойствами. Например, если \(W\)={a,ab}, то \(W\)* состоит из всех строк, в которых перед каждой буквой `b' идёт хотя бы одна буква `a'.

Задано некоторое множество строк \(W\). Требуется найти множество \(X\), такое, что \(W\)*=\(X\)* и множество \(X\) имеет минимальное возможное число элементов. В случае, если таких множеств несколько, подходит любое из них. Например, если \(W\)={a,aabb,ab,ac,b,bac}, то единственным множеством, удовлетворяющим условиям задачи будет множество {a,ac,b}.

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

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

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

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

Вася любит решать головоломки со спичками. Чаще всего они формулируется следующим образом: дано изображение \(A\), составленное из спичек; переложите в нем минимальное количество спичек так, чтобы получилось изображение \(B\).

Например, из номера текущего командного чемпионата школьников Санкт-Петербурга по программированию, можно получить ромб с диагональю, переложив всего три спички.

Головоломки, которые решает Вася, всегда имеют решение. Это значит, что набор спичек, используемый в изображении \(A\), совпадает с набором спичек, используемым в изображении \(B\). Кроме того, в одном изображении никогда не встречаются две спички, у которых есть общий участок ненулевой длины (то есть спички могут пересекаться, но не могут накладываться друг на друга).

Вася устал решать головоломки вручную, и теперь он просит вас написать, программу, которая будет решать головоломки за него. Программа будет получать описания изображений \(A\) и \(B\) и должна найти минимальное количество спичек, которые надо переложить в изображении \(A\), чтобы полученная картинка получалась из \(B\) параллельным переносом.

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

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

На данный момент у Сергея хранятся \(n\) точек восстановления различных серверов, пронумерованных от 1 до \(n\). Точка восстановления с номером \(i\) позволяет произвести откат для сервера \(a_i\). Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами \(l, l + 1, \ldots, r\) для некоторых \(l\) и \(r\).

Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного \(l\), при каком минимальном \(r\) в процессе переноса будут доступны точки восстановления не менее чем \(k\) различных серверов.

Помогите Сергею.