Jumping Robot

Flatland Dynamics is developing a jumping robot. The robot is tested on a circular route of $n$ special platforms, numbered from 1 to $n$. The distance between platform $i$ and platform $i+1$ is $d_i$, and the distance between platform $n$ and platform 1 is $d_n$.

The robot has an AI and learns to jump farther during the test. At any moment, the robot has an agility, which is an integer $a$. The robot can jump from platform $i$ to platform $i+1$ if $a \ge d_i$. Likewise, it can jump from platform $n$ to platform 1 if $a \ge d_n$. After each jump, the robot's agility increases by 1.

The developers choose one platform as the starting point. The experiment succeeds if the robot can make $n$ jumps, going from each platform to the next, complete the full circle, and return to the starting platform.

The developers want to know the minimum initial agility that lets the experiment succeed, and which platform the robot should start from.

The first line contains $n$ ($3 \le n \le 10^7$).

The second line contains an integer $f$ that describes how the distance array is given.

If $f = 1$, the third line contains $n$ integers $d_1, d_2, \ldots, d_n$ ($1 \le d_i \le 10^9$).

If $f = 2$, the third line contains an integer $m$ ($2 \le m \le \min(n, 10^5)$) and three integers $x$, $y$, and $z$ ($0 \le x, y, z \le 10^9$). The fourth line contains $m$ integers $c_1, c_2, \ldots, c_m$ ($1 \le c_i \le 10^9$). The distances are computed as follows.

If $1 \le i \le m$, then $d_i = c_i$.

If $m + 1 \le i \le n$, then $d_i = ((x \cdot d_{i-2} + y \cdot d_{i-1} + z) \bmod 10^9) + 1$. Here $\bmod$ is the remainder of integer division, written as % in C++, Java, and Python.

Print two integers. The first is the minimum initial agility $a$. The second is the number of a starting platform from which the experiment succeeds with that agility.

If several starting platforms work, print any of them.

In the second example, the distance array is $[1, 2, 3, 4, 5, 18, 45, 112, 273, 662]$. The values from $d_6$ to $d_{10}$ are computed as follows.

$d_6 = ((1 \cdot d_4 + 2 \cdot d_5 + 3) \bmod 10^9) + 1 = ((1 \cdot 4 + 2 \cdot 5 + 3) \bmod 10^9) + 1 = 18$

$d_7 = ((1 \cdot d_5 + 2 \cdot d_6 + 3) \bmod 10^9) + 1 = ((1 \cdot 5 + 2 \cdot 18 + 3) \bmod 10^9) + 1 = 45$

$d_8 = ((1 \cdot d_6 + 2 \cdot d_7 + 3) \bmod 10^9) + 1 = ((1 \cdot 18 + 2 \cdot 45 + 3) \bmod 10^9) + 1 = 112$

$d_9 = ((1 \cdot d_7 + 2 \cdot d_8 + 3) \bmod 10^9) + 1 = ((1 \cdot 45 + 2 \cdot 112 + 3) \bmod 10^9) + 1 = 273$

$d_{10} = ((1 \cdot d_8 + 2 \cdot d_9 + 3) \bmod 10^9) + 1 = ((1 \cdot 112 + 2 \cdot 273 + 3) \bmod 10^9) + 1 = 662$