Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t₁, t₂, …, t_n и набор из m строк-образцов s₁, s₂, …, s_m. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

Требуется написать программу, которая по заданному числу n, n словам словаря t₁, t₂, …, t_n, заданному числу m и m строкам-образцам s₁, s₂, …, s_m вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

Система телефонных номеров в России устроена следующим образом. Все телефонные номера имеют одну и ту же длину — M цифр. Номер состоит из двух частей: несколько первых цифр номера составляют код города, остальные цифры определяют номер абонента в пределах этого города.

В процессе развития сети коды городов регулярно меняются, при этом, коды различных городов обязательно различны. В остальном коды могут быть совершенно произвольными, в том числе код одного города может быть началом кода другого (например, код Нижнего Новгорода — 831, а код Сарова — 83130) и т. п. Если коды нескольких городов являются началом M-значного номера абонента, кодом города этого номера считается наидлиннейший из таких кодов. Так, если есть всего четыре города: Нижний Новгород, Балахна, Дзержинск и Саров с кодами, соответственно, 831, 83144, 8313 и 83130, и M = 9, то: телефоны 831123456 и 831412345 — телефоны Нижнего Новгорода, 831312345 — телефон Дзержинска, 831301234 — Сарова, а 831441234 — Балахны.

В этой задаче мы не будем учитывать различные другие ограничения на телефонные номера, существующие в реальности (например, в реальности никакой номер абонента в городе не может начинаться на 03, т. к. 03 — это телефон скорой помощи). Мы будем считать, что любой из 10^M возможных M-значных номеров является допустимым телефонным номером.

Нетривиальной задачей становится задача определения, сколько всего телефонных номеров может быть выдано в каждом городе. Например, в приведённом выше примере в Балахне и Сарове могут быть выданы 10 000 телефонных номеров (все четырёхзначные номера), в Дзержинске могут быть выданы 90000 телефонных номеров — все пятизначные телефонные номера, кроме начинающихся на ноль, а в Нижнем Новгороде могут быть выданы 890 000 номеров — все шестизначные номера, кроме тех, которые начинаются на цифру 3, а также на последовательность 44.

Напишите программу, которая решит эту задачу для произвольного набора кодов городов.

Цепочкой слов длины n назовем последовательность слов w₁, w₂, ..., w_n такую, что для 1 ≤ i ≤ n слово w_i является собственным префиксом слова w_i + 1.

Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.

Задано множество слов S = {s₁, s₂, ..., s_m}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.

Многие пользователи мобильных телефонов при наборе sms-сообщений используют режим T9. При этом сообщения, например на английском языке, они набирают следующим образом. Для набора слова по буквам соответствующая букве кнопка нажимается один раз, вне зависимости от того, сколько букв соответствуют этой кнопке, и какой по счету идет нужная буква (см. картинку), а программа в телефоне подбирает из имеющегося словаря подходящее для данной комбинации кнопок слово. Если подходящих слов несколько, то в первую очередь предлагается наиболее часто встречающееся слово (изначально слова одинаковой встречаемости предлагаются по алфавиту). Если слово не подошло, то пользователь нажимает кнопку ‘*’ и программа предлагает второе по встречаемости слово, образуемое той же комбинацией кнопок (в первую очередь следующее слово с той же частотой встречаемости, если такое имеется). Если и оно не подошло, то кнопка ‘*’ нажимается еще раз и т.д. Для простоты будем считать, что современные модели телефонов содержат полный словарь используемых слов, и нужное слово обязательно найдется. Когда предлагаемое слово подошло, пользователь нажимает на кнопку “пробел”, нажимает на кнопку ‘1’ (последняя соответствует набору знака препинания), или заканчивает набирать сообщение. Когда знак препинания не подошёл, опять же нажимается кнопка ‘*’, до тех пор пока не появится требуемый знак. После набора пробела или знака препинания пользователь может ввести ещё один пробел или знак препинания, начать набирать следующее слово или закончить набирать сообщение. Будем считать, что пользователю достаточно трех знаков препинания, и они предлагаются в следующем порядке: точка (‘.’), запятая (‘,’), вопросительный знак (‘?’). После того как пользователь “утвердил” набранное слово (нажав на пробел или ‘1’), частота его встречаемости в словаре увеличивается на 1, и новое значение частоты учитывается, в том числе, и при наборе в режиме T9 остальных слов того же сообщения. При этом данное слово будет предлагаться первым среди слов с такой же частотой встречаемости, порядок предложения остальных слов остается неизменным. Когда появится еще одно слово с той же частотой, то уже оно будет предлагаться первым, не меняя порядка остальных, и т. д. Вам требуется написать программу, которая по имеющемуся словарю, содержащему первоначальные характеристики частоты встречаемости того или иного английского слова, и известной последовательности нажатий кнопок пользователем при наборе sms-сообщения в режиме T9 воспроизведет появившееся на экране сообщение.

Одна из новых возможностей текстового редактора «World XP» — это сортировка слов в предложении. Выход новой бета-версии редактора должен состоятся не позднее, чем через пять часов, а заявленная функция еще не реализована.

Требуется написать программу, осуществляющую сортировку слов в предложении. При этом все символы, отличные от букв, должны сохранится и не поменять своего положения относительно вхождений слов. Для упрощения при подаче входных данных на вход вашей программы все такие символы будут заменены на символ «.» (точка). Таким образом символ «.» имеет смысл разделителя между словами. Например, строка «..aba.a..ba» после сортировки пример вид «..a.aba..ba», а строка «c..bb.a» примет вид «a..bb.c». Слова следует сортировать лексикографически, как в словаре.