Задача A2. Прыгающий робот

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Компания «Flatland Dynamics» разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из n специальных платформ, пронумерованных от 1 до n. Расстояние между i-й и i + 1-й платформой равно di, аналогично расстояние между n-й и 1-й платформой равно dn.

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом a. Робот может перепрыгнуть с платформы i на платформу i + 1, если a ≥ di. Аналогично, прыжок с n-й платформы на 1-ю возможен, если a ≥ dn. При этом после каждого прыжка ловкость робота увеличивается на~1.

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

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

На первой строке ввода находится число n (3 ≤ n ≤ 107).

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

Если f = 1, то на третьей строке находятся n целых чисел d1, d2, …, dn (1 ≤ di ≤ 109).

Если f = 2, то на третьей строке находится число m (2 ≤ m ≤ min(n, 105)) и три целых числа x, y и z (0 ≤ x, y, z ≤ 109). На четвертой строке находятся m целых чисел c1, c2, …, cm (1 ≤ ci ≤ 109). Значения di вычисляются по следующим формулам.

Если 1 ≤ i ≤ m, то di = ci.

Если m + 1 ≤ i ≤ n, то di = ((x⋅ di − 2 + y⋅ di − 1 + z)mod 109) + 1.

Здесь mod означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом «%».

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

Требуется вывести два целых числа: минимальную допустимую начальную ловкость a и номер стартовой платформы, на которую можно разместить робота, чтобы успешно провести эксперимент.

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

Ограничения

Система оценки

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
115n ≤ 300, f = 1, di ≤ 300первая ошибка
217n ≤ 5000, f = 11первая ошибка
310 n ≤ 100 000, f = 1, гарантируется, что оптимально начать с первой платформыпервая ошибка
420n ≤ 100 000, f = 11 — 3первая ошибка
55f = 2, гарантируется, что оптимально начать с первой платформы3первая ошибка
633f = 21 — 5первая ошибка

Пояснение к примеру

Во втором примере массив расстояний между платформами равен [1, 2, 3, 4, 5, 18, 45, 112, 273, 662]. Значения от d6 до d10 вычисляются по формулам:

d6 = ((1⋅ d4 + 2⋅ d5 + 3mod 109) + 1 = ((1⋅ 4 + 2⋅ 5 + 3)mod 109) + 1 = 18

d7 = ((1⋅ d5 + 2⋅ d6 + 3mod 109) + 1 = ((1⋅ 5 + 2⋅ 18 + 3)mod 109) + 1 = 45

d8 = ((1⋅ d6 + 2⋅ d7 + 3mod 109) + 1 = ((1⋅ 18 + 2⋅ 45 + 3)mod 109) + 1 = 112

d9 = ((1⋅ d7 + 2⋅ d8 + 3mod 109) + 1 = ((1⋅ 45 + 2⋅ 112 + 3)mod 109) + 1 = 273

d10 = ((1⋅ d8 + 2⋅ d9 + 3mod 109) + 1 = ((1⋅ 112 + 2⋅ 273 + 3)mod 109) + 1 = 662

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

Стандартный вход Стандартный выход
1
5
1
3 7 4 2 5
4 3
2
10
2
5 1 2 3
1 2 3 4 5
653 1

0.092s 0.012s 15