Задача A. Грузоперевозки ≡

Условие

Стивен устроился на работу программистом в новую транспортную компанию. В его обязанности входит оптимизация стоимости грузоперевозок из одной страны в другую.

В базе данных компании содержатся N городов, пронумерованных от 1 до N, и M односторонних дорог между некоторыми из них. Дорога номер i характеризуется тремя числами u_i v_i l_i — начальным городом, конечным городом и длиной дороги. Гарантируется, что u_i ≠ v_i, и не существует двух разных дорог i, j, для которых u_i = u_j, v_i = v_j.

Страна представляет из себя такое множество из одного или более городов, что:

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

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

Запрос на перевозку определяется парой чисел s_j f_j — номерами города отправления и города назначения j-го груза. Напишите программу, которая для каждого из Q запросов определяет наименьшую возможную стоимость перевозки груза.

В тесте из примера имеется две страны. Одна состоит из городов 1, 2, 3, другая — из городов 4, 5.

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

Входной файл содержит целые числа N M — количество городов и дорог соответственно.

Далее следует M троек целых чисел u_i v_i l_i — начальный город, конечный город и длина i-й дороги.

Далее следует целое число Q, за котором идут Q запросов по два целых числа s_j f_j — город отправления и город назначения j-го груза.

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

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

Ограничения

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

5 6
1 2 1
2 3 3
3 1 3
1 4 2
4 5 1
5 4 2
4
2 5
1 3
4 1
1 1

2
0
-1
0

Задача B. Дед Мазай и зайцы ≡

Условие

Дед Мазай давно живёт в деревне Малые Вежи. Так давно, что он составил карту высот окрестностей.

Карта представляет собой прямоугольник n × m клеток (n клеток в высоту и m клеток в ширину). Для клетки, находящейся в i-ом ряду на j-ой колонке, отмечена высота h_i,j местности в этой клетке над уровнем реки (в метрах). Известно, что для всех i выполняется соотношение h_i,1 = 0. То есть, изначально рекой затоплены те и только те клетки, которые располагаются в самом левом столбце карты.

На реке начался паводок. Уровень реки поднимается на 1 метр каждую минуту, затопляя окрестности. А именно, если клетка (i, j) соседствует с клеткой, затопленой рекой, и уровень реки уже достиг или превысил h_i,j, то считается, что клетка (i, j) также затоплена рекой. Клетки считаются соседними, если у них имеется одна общая сторона.

В начале паводка дед Мазай в своей лодке находится в клетке (1; 1) — в левом верхнем углу карты. За одну минуту дед Мазай может перебраться на соседнюю клетку, если она уже затоплена рекой или будет затоплена рекой к моменту окончания перехода.

Зайцы в начале паводка располагаются в клетке (i_r, j_r), j_r > 1. Обычно зайцы стоят на месте, но если на следующей минуте их клетка окажется затоплена рекой, то они пытаются перейти на соседнюю клетку, которая не будет затоплена рекой. Если таких клеток несколько, то они выбирают из них первую в следующем списке: верхняя, правая, нижняя, левая. Если соседних клеток, которые на следующей минуте не будут затоплены рекой, не существует, то зайцы утонут.

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

Вы находитесь в безопасности в доме Деда Мазая. Перед глазами у вас карта и вам известно, где находятся зайцы. У вас есть связь по рации с Дедом Мазаем. Сообщите ему поминутный список перемещений, которые надо совершить, чтобы спасти зайцев; либо сообщите, что зайцев спасти невозможно. Если существует несколько решений, выведите любое из них. Решение должно заканчиваться позицией, в которой дед Мазай находится на соседней с зайцами клетке, и их клетка не затоплена рекой.

Зайцы никогда не выходят за пределы карты. Деду Мазаю также не разрешается выводить свою лодку за пределы карты.

В первом примере дед Мазай подплывает к зайцам через 4 минуты. Уровень реки в этот момент равен 4 метрам, и в следующую минуту река затопит всю местность. Зайцы оказываются спасены.

Во втором примере дед Мазай перемещается на одну клетку вправо и ждёт пока зайцы сами окажутся рядом с ним, спасаясь от потопа.

Во третьем примере, спасаясь от потопа, зайцы убегают в направлении от деда Мазая. Как бы дед Мазай ни действовал, он не успевает спасти зайцев.

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

В начале входного файла записаны целые числа n, m, i_r, j_r. Далее следует nm целых чисел h_i,j — карта.

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

Если зайцев можно спасти, то выведите строку с инструкциями для деда Мазая. Каждый символ строки обозначает, что должен делать дед Мазай в очередную минуту:

• S — остаться на месте;
• U — сдвинутся на одну клетку вверх;
• R — сдвинутся на одну клетку вправо;
• D — сдвинутся на одну клетку вниз;
• L — сдвинутся на одну клетку влево.

Если зайцев спасти невозможно, выведите единственное слово "NO".

Ограничения

1 ≤ n, m ≤ 500;

1 ≤ i_r ≤ n;

2 ≤ j_r ≤ m;

1 ≤ h_i,j ≤ 10⁵ при j > 2;

h_i,1 = 0;

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

3 3 2 3
0 5 5
0 5 5
0 1 1

DDRR

5 4 5 2
0 1 1 1
0 4 5 6
0 3 1 1
0 2 1 1
0 1 1 1

RSS

4 2 2 2
0 1
0 1
0 2
0 3

NO

Problem C. Knuth-Morris-Pratt ≡

Statement

Input file format

Output file format

Constraints

Sample tests

yezhiki nachinayut i vyygryvayut
yut

16

Problem D. 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

Задача E. Поврежденный 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>