Прыгающий робот

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

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

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

Входные данные

На первой строке входного файла INPUT.TXT находится число n (3 ≤ n ≤ 10⁷).

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

Если f = 1, то на третьей строке находятся n целых чисел d₁, d₂, ... , d_n (1 ≤ d_i ≤ 10⁹).

Если f = 2, то на третьей строке находится число m (2 ≤ m ≤ min(n, 10⁵)) и три целых числа x, y и z (0 ≤ x, y, z ≤ 10⁹). На четвертой строке находятся m целых чисел c₁, c₂, ... , c_m (1 ≤ c_i ≤ 10⁹). Значения d_i вычисляются по следующим формулам.

Если 1 ≤ i ≤ m, то d_i = c_i.

Если m + 1 ≤ i ≤ n, то d_i = ((x · d_i−2 + y · d_i−1 + z) mod 10⁹) + 1.

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

Выходные данные

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

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

Примеры

Пояснение

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

d₆ = ((1 · d₄ + 2 · d₅ + 3) mod 10⁹) + 1 = ((1 · 4 + 2 · 5 + 3) mod 10⁹) + 1 = 18

d₇ = ((1 · d₅ + 2 · d₆ + 3) mod 10⁹) + 1 = ((1 · 5 + 2 · 18 + 3) mod 10⁹) + 1 = 45

d₈ = ((1 · d₆ + 2 · d₇ + 3) mod 10⁹) + 1 = ((1 · 18 + 2 · 45 + 3) mod 10⁹) + 1 = 112

d₉ = ((1 · d₇ + 2 · d₈ + 3) mod 10⁹) + 1 = ((1 · 45 + 2 · 112 + 3) mod 10⁹) + 1 = 273

d₁₀ = ((1 · d₈ + 2 · d₉ + 3) mod 10⁹) + 1 = ((1 · 112 + 2 · 273 + 3) mod 10⁹) + 1 = 662

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки] [Решение]