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

Условие

Компания «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 прыжков от текущей платформы к следующей, завершить полный круг и вернуться на ту же платформу. Разработчикам необходимо выяснить, для какого минимального значения начальной ловкости робота им удастся провести эксперимент и с какой платформы роботу следует начать прыжки.

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

На первой строке ввода находится число 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 он обозначается символом «%».

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

Требуется вывести два целых числа: минимальную допустимую начальную ловкость 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

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

5
1
3 7 4 2 5

4 3

10
2
5 1 2 3
1 2 3 4 5

653 1