점프하는 로봇

Flatland Dynamics사는 점프하는 로봇을 개발한다. 시험에는 번호가 1부터 $n$까지 붙은 특수 플랫폼 $n$개로 이루어진 원형 코스를 쓴다. 플랫폼 $i$와 $i+1$ 사이의 거리는 $d_i$이고, 플랫폼 $n$과 1 사이의 거리는 $d_n$이다.

로봇에는 AI가 들어 있어서 시험 중에 더 멀리 뛰도록 학습한다. 로봇은 어느 순간이든 정수 $a$로 나타내는 민첩성을 가진다. $a \ge d_i$이면 로봇은 플랫폼 $i$에서 $i+1$로 뛸 수 있다. 마찬가지로 $a \ge d_n$이면 플랫폼 $n$에서 1로 뛸 수 있다. 한 번 뛸 때마다 로봇의 민첩성은 1 증가한다.

개발자는 시작 플랫폼을 하나 고른다. 로봇이 플랫폼을 차례로 $n$번 뛰어 한 바퀴를 돌고 시작 플랫폼으로 돌아오면 실험은 성공이다.

개발자는 실험을 성공시킬 수 있는 초기 민첩성의 최솟값과, 로봇을 어느 플랫폼에서 출발시켜야 하는지 알고 싶어 한다.

첫째 줄에 $n$ ($3 \le n \le 10^7$)이 주어진다.

둘째 줄에는 거리 배열이 주어지는 형식을 나타내는 정수 $f$가 주어진다.

$f = 1$이면 셋째 줄에 정수 $d_1, d_2, \ldots, d_n$ ($1 \le d_i \le 10^9$) $n$개가 주어진다.

$f = 2$이면 셋째 줄에 정수 $m$ ($2 \le m \le \min(n, 10^5)$)과 정수 $x$, $y$, $z$ ($0 \le x, y, z \le 10^9$)가 주어진다. 넷째 줄에는 정수 $c_1, c_2, \ldots, c_m$ ($1 \le c_i \le 10^9$) $m$개가 주어진다. 거리는 다음과 같이 계산한다.

$1 \le i \le m$이면 $d_i = c_i$이다.

$m + 1 \le i \le n$이면 $d_i = ((x \cdot d_{i-2} + y \cdot d_{i-1} + z) \bmod 10^9) + 1$이다. 여기서 $\bmod$는 나머지 연산이며, C++, Java, Python에서는 %로 쓴다.

정수 두 개를 출력한다. 첫 번째는 최소 초기 민첩성 $a$이다. 두 번째는 그 민첩성에서 실험에 성공하는 시작 플랫폼의 번호이다.

성공하는 시작 플랫폼이 여럿이면 그중 아무 번호나 출력해도 된다.

두 번째 예제의 거리 배열은 $[1, 2, 3, 4, 5, 18, 45, 112, 273, 662]$이다. $d_6$부터 $d_{10}$은 다음과 같이 계산된다.

$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$