Задача A. groupby group ≡

Условие

Необходимо написать программу, которая группирует студентов по их группам.

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

В первой строке входного файла дано число n — количество студентов. Далее следует n строк, в каждой из которых записаны группа и имя студента.

Группа и имя студента разделены символом табуляции.

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

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

Сами группы следуют также в алфавитном порядке.

Ограничения

1 ≤ n ≤ 10⁵

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

3
M8103	Sidorov Sidor
M8888	Petrov Petr
M8103	Ivanov Ivan

M8103
Ivanov Ivan
Sidorov Sidor
M8888
Petrov Petr

Задача B. Длинная прогрессия ≡

Условие

Задана последовательность состоящая из N натуральных чисел A_i. Необходимо определить, можно ли, переставляя элементы этой последовательности, выстроить их в отрезок неубывающей арифметической прогрессии.

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

В первой строке входного файла содержится число N

Во второй строчке входного файла содержатся N чисел, задающие входную последовательность

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

В выходном файле должно содержаться:

• Единственное число  − 1 — если прогрессию построить невозможно
• Два целых числа A D (A — первый член последовательности, D — шаг прогрессии), то есть искомая прогрессия состоит из чисел A, A + D, A + 2 * D, …, A + (N − 1) * D — в противном случае

Ограничения

2 ≤ N ≤ 10⁵

0 ≤ |A_i| ≤ 10⁶

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

9
80 50 10 30 70 40 20 60 90

10 10

Задача C. Будь как все ≡

Условие

Дан массив чисел. Нужно заменить в нем максимальный элемент на минимальный из этого же массива. Если максимальных несколько — заменить каждый из них.

Формат входных данных

Входные данные содержат несколько чисел, разделенных пробелами.

Формат выходных данных

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

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

3 -1 2 4 9 6

3 -1 2 4 -1 6

5 4 1 5 2

1 4 1 1 2

Задача D. Библиотекарь ≡

Условие

Аполлинарий Матвеевич — старый, седой библиотекарь. Сегодня он в очень хорошем настроении, потому что библиотеке подарили компьютер.

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

Однажды в библиотеку зашёл читатель. Он дал Аполлинарию Матвеевичу список тем и попросил его подобрать книги по этим темам. Аполлинарий Матвеевич обрадовался: у него есть база данных! Но стоп: как найти в базе данных нужную информацию? Для этого нужна программа.

Помогите Аполлинарию Матвеевичу. Напишите программу, позволяющую определить, к каким областям относятся заданные темы и в каких книгах можно найти информацию по этим темам.

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

Первая строка входного файла содержит целое число N — количество областей знаний.

Далее для каждой области знаний входной файл содержит название области знаний, за которым следует количество книг, относящихся к данной области знаний.

Далее для каждой книги входной файл содержит название книги, за которым следует количество тем, затронутых в данной книге. Далее следует список тем.

Далее входной файл содержит целое число M — количество тем в списке, подготовленном читателем. Далее следует список тем.

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

Для каждой темы требуется вывести строку "Topic: название темы". Далее должна следовать строка "Subject: название области знаний". Далее должна следовать строка "Books:" (без пробелов). Далее должен следовать список книг в том порядке, в котором они перечислены во входном файле.

Ограничения

1 ≤ N ≤ 50

1 ≤ M ≤ 10

Количество книг, относящихся к определённой области знаний, от 1 до 100.

Количество тем, затронутых в определённой книге, от 1 до 10.

Все названия во входном файле имеют длину от 1 до 50 символов и состоят из маленьких латинских букв.

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

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

2
mathematics
2
algebra
3
lines
equations
coordinates
geometry
3
triangles
coordinates
lines
physics
2
mechanics
3
force
velocity
mass
gravitation
2
force
mass
5
force
triangles
velocity
coordinates
mass

Topic: force
Subject: physics
Books:
mechanics
gravitation
Topic: triangles
Subject: mathematics
Books:
geometry
Topic: velocity
Subject: physics
Books:
mechanics
Topic: coordinates
Subject: mathematics
Books:
algebra
geometry
Topic: mass
Subject: physics
Books:
mechanics
gravitation

Задача E. Ежеминутные автобусы ≡

Условие

На автобусную остановку каждую минуту подходит автобус одного из маршрутов. Диспетчерская служба собрала данные за N минут — номера маршрутов каждого автобуса.

Требуется определить максимально возможное время ожидания для пассажира, желающего уехать определённым маршрутом. Т.е. в данной последовательности номеров маршрутов нужно найти два самых удаленных числа, равных между собой. Например, для последовательности 2, 11, 2, 2, 25, 11, 25, 11 максимальное время ожидания равно 4 — для маршрута номер 11.

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

Входной файл содержит число N, за которыми следует N чисел a_i — номера маршрутов.

Все числа целые. Каждый номер маршрута встречается не менее двух раз.

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

Ограничения

2 ≤ i ≤ 10⁶

1 ≤ a_i ≤ 100

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

8
2 11 2 2 25 11 25 11

4

4
23 23 41 41

1

Задача F. Дифтонги ≡

Условие

Слова марсианского языка состоят из малых латинских букв. Буквы a, e, i, o, u, y считаются гласными, остальные — согласными.

Дифтонгом называется пара подряд идущих гласных букв, окружённых либо согласными буквами, либо границами слова. Например, в слове preemptio имеется два дифтонга, а в слове aaa — ни одного.

Требуется среди N данных слов найти те, в которых количество дифтонгов максимально.

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

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

Ограничения

1 ≤ N ≤ 100

Слова содержат от 1 до 255 символов.

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

3
e
ee
eee

ee

3
aabbee
cyydyyy
xiixiixiii

aabbee
xiixiixiii

Problem G. Elementary arithmetic ≡

Statement

Underwater arithmetic is very elementary. There are just two operations: WITH and WITHOUT which mean addition and subtraction respectively.

Underwater mathematicians did not yet invent brackets, so all expressions are calculated from right to left. For example, the expression 3 WITH 5 WITHOUT 4 WITHOUT 7 is calculated as (3 + (5 − (4 − 7))).

Scientists of Nearsea Institute of Underwater Arithmetic need a program to evaluate such expressions.

Input file format

First line of input file contains a single integer N. Following 2 × N + 1 lines describe the expression. Odd lines contain integer operands, even lines contain operations.

Output file format

Output file must contain a single integer — calculation result.

Constraints

1 ≤ N ≤ 10³

All operands are in range from 0 to 10³.

Sample tests

1
2
WITH
3

5

3
10
WITHOUT
5
WITH
3
WITH
15

-13

Задача H. Три самые популярные книги ≡

Условие

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

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

Входной файл содержит целое число N, за которым следуют N целых чисел B₁ B₂… B_N — номера проданных книг. Среди этих номеров найдутся хотя бы три различных.

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

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

Ограничения

3 ≤ N ≤ 10000, 1 ≤ B_i ≤ 10000

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

3 123 456 789

123 456 789

6 6 7 7 8 8 8

8 7 6

10 13 15 12 18 10 13 19 12 12 19

12 13 19