Строка 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 вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

На окружности отмечено \(2n\) различных точек, пронумерованных от 1 до \(2n\) против часовой стрелки. Петя нарисовал \(n\) хорд, \(i\)-я из которых соединяет точки с номерами \(a_i\) и \(b_i\). При этом каждая точка является концом ровно одной хорды.

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

Напомним, что палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, палиндромами являются строки “abba” и “madam”.

Для произвольной строки \(s\) введем операцию деления пополам, обозначаемую \(half(s)\). Значение \(half(s)\) определяется следующими правилами:

Если \(s\) не является палиндромом, то значение \(half(s)\) не определено;

Если \(s\) имеет длину 1, то значение \(half(s)\) также не определено;

Если \(s\) является палиндромом четной длины \(2m\), то \(half(s)\) — это строка, состоящая из первых \(m\) символов строки \(s\);

Если \(s\) является палиндромом нечетной длины \(2m+1\), большей \(1\), то \(half(s)\) — это строка, состоящая из первых \(m + 1\) символов строки \(s\).

Например, значения \(half(\mbox{inforamatics})\) и \(half(\mbox{i})\) не определены, \(half(\mbox{abba}) = \mbox{ab}\), \(half(\mbox{madam}) = \mbox{mad}\).

Палиндромностью строки \(s\) будем называть максимальное число раз, которое можно применить к строке \(s\) операцию деления пополам, чтобы результат был определен.

Например, палиндромность строк “informatics” и “i” равна 0, так как к ним нельзя применить операцию деления пополам даже один раз. Палиндромность строк “abba” и “madam” равна 1, а палиндромность строки “totottotot” равна 3, поскольку операция деления пополам применима к ней три раза: “totottotot” → “totot” → “tot” → “to”.

Рассмотрим все строки длины \(n\), состоящие из строчных латинских букв, палиндромность которых равна \(p\). Ваша задача — найти \(k\)-ю в алфавитном порядке среди этих строк.

В театре работает \(n\) актеров. Известно, что среди них \(a\) – высоких, \(b\) – голубоглазых и \(с\) – блондинов. Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин. Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать, какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.

Требуется написать программу, которая по заданным числам \(n\), \(a\), \(b\) и \(с\) определяет минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.

2
5 3 4 5

3

1
5 3 4 5

2