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

Компания <<Flatland Dynamics>> разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из $n$ специальных платформ, пронумерованных от $1$ до $n$. Расстояние между $i$-й и $i+1$-й платформой равно $d\_i$, аналогично расстояние между $n$-й и $1$-й платформой равно $d\_n$.

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

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

На первой строке ввода находится число $n$ ($3 \le n \le 10^7$).

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

Если $f = 1$, то на третьей строке находятся $n$ целых чисел $d\_1, d\_2, \ldots, d\_n$ ($1 \le d\_i \le 10^{9}$).

Если $f = 2$, то на третьей строке находится число $m$ $\left(2 \le m \le \min(n, 10^5)\right)$ и три целых числа $x$, $y$ и $z$ ($0 \le x, y, z \le 10^9$). На четвертой строке находятся $m$ целых чисел $c\_1, c\_2, \ldots, c\_m$ ($1 \le c\_i \le 10^9$). Значения $d\_i$ вычисляются по следующим формулам. 

Если $1 \le i \le m$, то $d\_i = c\_i$. 

Если $m + 1 \le i \le n$, то $d\_i = \left((x\cdot d\_{i-2} + y\cdot d\_{i-1} + z)\bmod 10^9\right) + 1$. 

Здесь $\bmod$ означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом <<\%>>.

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

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

Во втором примере массив расстояний между платформами равен $\[1, 2, 3, 4, 5, 18, 45, 112, 273, 662]$. Значения от $d\_6$ до $d\_{10}$ вычисляются по формулам:

$d\_6 = \left((1\cdot d\_4+2\cdot d\_5 + 3) \bmod 10^9\right)+1 = \left((1\cdot 4+2\cdot 5+3)\bmod 10^9\right)+1=18$

$d\_7 = \left((1\cdot d\_5+2\cdot d\_6 + 3) \bmod 10^9\right)+1 = \left((1\cdot 5+2\cdot 18+3)\bmod 10^9\right)+1=45$

$d\_8 = \left((1\cdot d\_6+2\cdot d\_7 + 3) \bmod 10^9\right)+1 = \left((1\cdot 18+2\cdot 45+3)\bmod 10^9\right)+1=112$

$d\_9 = \left((1\cdot d\_7+2\cdot d\_8 + 3) \bmod 10^9\right)+1 = \left((1\cdot 45+2\cdot 112+3)\bmod 10^9\right)+1=273$

$d\_{10} = \left((1\cdot d\_8+2\cdot d\_9 + 3) \bmod 10^9\right)+1 = \left((1\cdot 112+2\cdot 273+3)\bmod 10^9\right)+1=662$