Задача A. Префикс-функция ≡

Условие

Дана строка s. Найдите сумму значений префикс-функции для всех позиций строки s.

Формат входного файла

Во входном файле записана единственная строка s.

Формат выходного файла

В выходной файл выведите одно число — ответ на задачу.

Ограничения

1 ≤ |s| ≤ 150000

Примеры тестов

abcaabacabc

11

Problem B. Knuth-Morris-Pratt ≡

Statement

Input file format

Output file format

Constraints

Sample tests

yezhiki nachinayut i vyygryvayut
yut

16

Problem C. Banner scrolling ≡

Statement

Young web developer Vasya was hired by "Dalstolb" company. Company maintains a popular news website with many advertisement banners. Marketing department of "Dalstolb" has proposed a new idea for animated transition between two text messages on the banner.

Message is a single line of characters. First message has length L₁, second has length L₂ ≥ L₁. Since the banner width is only enough to fit L₁ characters, the message after the transition should contain any substring the second message of length L₁. Transition should be performed as a series of animation frames. Each frame, message is either scrolled to the right by removing leftmost character and appending arbitrary new character from the right, or scrolled to the left by removing rightmost character and appending arbitrary new character from the left.

You program must, given two messages, find a shortest possible transition between them.

Input file format

First line of the input file contains the first message. Second line of the input file contains the second message. Messages are composed of small Latin letters.

Output file format

First line of output file must contain integer N — minimum number of frames. Following N lines must contain two-character string each — frame descriptions. First character must be either L or R, denoting right or left scrolling correspondingly. Second character must be a small Latin letter which should be appended to the message.

Constraints

1 ≤ L₁ ≤ L₂ ≤ 2000;

Sample tests

acm
solutionaccepted

1
Ln

vvostoker
vladivostok

4
Rz
Li
Ld
La

Задача D. Нормальная палиндромика ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

abcc

ba

abcd

cba

Problem E. Fibonacci level ≡

Statement

For arbitrary non-empty strings S₁ and S₂, the Fibonacci sequence of strings is defined by a recurrence S_i + 2 = S_i + 1 + S_i, where the '+' sign denotes string concatenation.

Let's say that string T has Fibonacci level n if there exists some Fibonacci sequence of strings which contains S_n = T. Note that any string of length 2 or more has Fibonacci level 3.

Your program must, given a string T, find its maximum Fibonacci level n as well as two starting strings S₁ and S₂ of corresponding Fibonacci sequence of strings.

Input file format

Input file contains a single string T, consisting of lowercase Latin letters.

Output file format

Output file must contain 3 lines: integer n followed by strings S₁ and S₂.

If there are several optimal solutions, output any of them.

Constraints

2 ≤ |T| ≤ 10⁶

Sample tests

oxax

3
xax
o

cabccab

5
ab
c

axaxax

4
ax
ax

Задача F. Длинный текст и много слов (revisited) ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

longlongstring
2
short
string

0 1

Задача G. Поврежденный XML ≡

Условие

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки  <  (ASCII 60), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка  >  (ASCII 62). Примеры открывающих тегов:  < a > ,  < dog > .

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш / (ASCII 47), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов:  < /a > ,  < /dog > .

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

• Пустая строка является корректной XML-строкой.
• Если A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
• Если A — корректная XML-строка, то строка  < X > A < /X > , получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.

Например, представленные ниже строки:

•  < a >  < /a > 
•  < a >  < ab >  < /ab >  < c >  < /c >  < /a > 
•  < a >  < /a >  < a >  < /a >  < a >  < /a > 

•  < a >  < /b > 
•  < a >  < b > 
•  < a >  < b >  < /a >  < /b > 

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.

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

Формат входного файла

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

Формат выходного файла

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

Ограничения

Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы  < ,  >  и /.

Примеры тестов

<a></b>

<b></b>

<a><aa>

<a></a>

<a><>a>

<a></a>

<a/</a>

<a></a>

Задача H. Abracadabra ≡

Условие

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

Система оценивания

Правильные решения для тестов, в которых 1 ≤ n ≤ 100, 1 ≤ m ≤ 100, будут оцениваться из 30 баллов.

Формат входного файла

Первая строка входного файла содержит целое число n. Последующие n строк содержат слова t₁, t₂, …, t_n, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 10⁶. Словарь не содержит пустых слов.

Затем следует строка, содержащая целое число m. Последующие m строк содержат строки-образцы s₁, s₂, …, s_m, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 10⁶. Никакая строка-образец не является пустой строкой.

Формат выходного файла

Выходной файл должен содержать m чисел, по одному на строке. Для каждой строки-образца в порядке, в котором они заданы во входном файле, следует вывести количество слов словаря, для которых она является супрефиксом.

Ограничения

1 ≤ n, m ≤ 200 000

Примеры тестов

4
abacaba
abracadabra
aa
abra
3
a
abra
abac

4
2
0