Задача A. Правильная запись номера ≡

Условие

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

Российский телефонный номер в международном формате выглядит следующим образом: +7␣код_региона␣локальный_номер. В зависимости от длины кода региона существует 4 допустимых варианта записи:

• +7␣123␣123-45-67
• +7␣1234␣12-34-56
• +7␣12345␣1-23-45
• +7␣123456␣12-34

Сотрудник отдела кадров НИИ АСМ просит Вас написать программу, конвертирующую телефонный номер в международный формат.

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

Входной файл содержит единственную строчку с телефонным номером.

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

Выходной файл должен содержать единственную строчку — телефонный номер в международном формате.

Ограничения

Каждый телефонный номер работника начинается с подстроки +7 после которой следует код региона и локальный номер. Код региона — первый блок подряд идущих цифр после +7. В качестве символов разделителя могут быть использованы пробелы (ASCII 32) и тире (ASCII 45). Код региона может быть также обрамлён круглыми скобками (ASСII 40 и ASСII 41), в этом случае символы разделителя вокруг скобок могут быть опущены.

Суммарное количество цифр в коде региона и локальном номере равно 10. Длина входной строки не превышает 25 символов.

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

+7 (123)456-7-890

+7 123 456-78-90

+7(9876)543 210

+7 9876 54-32-10

+7-31415 92 - 65-3

+7 31415 9-26-53

Задача B. Гвоздики ≡

Условие

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

В первой строке входного файла записано число N — количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел  — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10 000).

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

В выходной файл нужно вывести единственное число — минимальную суммарную длину всех ниточек.

Ограничения

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

5
4 10 0 12 2

6

Задача C. Арифметическая прогрессия ≡

Условие

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

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

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

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

Напомним что последовательность a₁, a₂, …, a_n называется арифметической прогрессией, если a_i = a_i−1 + d для всех i от 2 до n и некоторого d. Число d называется разностью арифметической прогрессии.

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

В первой строке входного файла находится целое число n (1 ≤ n ≤ 100 000). В следующей строке находится 2 n целых чисел по модулю не превосходящих 10⁹ — числа, написанные на карточках, перечисленные в произвольном порядке. Гарантируется, что можно выбрать n из них так, чтобы они образовывали арифметическую прогрессию.

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

В первой строке выходного файла выведите a₁ и d — первый элемент и разность найденной арифметической прогрессии. Если d = 0, число a₁ должно встречаться среди заданных чисел n раз.

Если существует несколько решений, выведите любое.

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

3
8 7 1 5 4 3

1 3

Задача D. Безопасная поездка ≡

Условие

Вам требуется успеть на важную встречу. Сейчас вы находитесь в точке 0, встреча пройдёт в точке с координатой D метров через T секунд. Но есть ещё одна проблема: светофоры.

Начиная с момента 0, светофор с номером i сначала показывает красный свет в течение a_i секунд, затем зелёный в течение b_i секунд, а затем процесс повторяется. В момент смены сигнала считается, что продолжает гореть предыдущий сигнал.

Чтобы максимизировать безопасность дороги (а также снизить риск получения штрафа) требуется найти минимальную скорость, с которой потребуется двигаться, чтобы успеть вовремя.

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

В первой строке записаны целые числа T, D и N "--- время до встречи, координата места встречи и число светофоров (1 ≤ T ≤ 10⁹, 1 ≤ D ≤ 10⁹, 0 ≤ N ≤ 50).

В следующих N строках записано по три целых числа a_i, b_i, p_i "--- длительность красного и зелёного сигналов i-го светофора и его положение на пути до встречи (1 ≤ a_i, b_i ≤ 10⁹, 1 ≤ p_i ≤ 10⁹). Позиции светофоров не совпадают, в точке D светофора нет.

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

Выведите единственное целое число "--- минимальную скорость. Абсолютная или относительная погрешность не должна превышать 10⁻⁵. Если добраться вовремя невозможно, выведите −1.0.

Ограничения

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

10 10 1
3 4 3

1.0

12 16 2
2 3 2
3 2 9

1.7500000000000004

12 13 5
1 2 3
2 2 5
3 3 7
1 6 9
3 4 11

1.25