Background

Translated from ROIR 2022 D1T2。

A company is developing a jumping robot. To test the robot, they set up a circular route on a polygonal platform, consisting 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 the last platform and the first platform is $d_n$ (assume that edges with lengths $d_1, d_2, \dots, d_n$ can form an $n$-gon)。

The robot is equipped with artificial intelligence and learns to jump farther during testing. At any moment, the robot uses an integer $a$ to represent its sensitivity. If $a$ is greater than or equal to $d_i$, the robot can jump from platform $i$ to platform $i+1$; similarly, if $a$ is greater than or equal to $d_n$, the robot can jump from the last platform to the first platform. After each jump, the robot's sensitivity increases by $1$。

Problem Description

The robot's developers choose one platform as the starting platform. If the robot can complete $n$ jumps and return to the original platform, they consider the experiment successful. The developers need to determine the minimum initial sensitivity of the robot, and which platform to choose as the starting platform。

Input Format

The first line contains an integer $n$。

The second line contains an integer $f$。

• If $f = 1$, then the third line contains $n$ integers $d_1, d_2, \dots, d_n$, as described in the Background.
• If $f = 2$, then the third line contains an integer $m$ and three integers $x, y, z$. The fourth line contains $m$ integers $c_1, c_2, \dots, c_m$. In this case, the distance values $d_i$ are computed by the following formulas:
  • If $1 \le i \le m$, then $d_i = c_i$。
  • If $m + 1 \le i \le n$, then $d_i = ((x \times d_{i−2} + y \times d_{i−1} + z) \bmod 10^9) + 1$。

Output Format

Output two integers: the minimum allowed initial sensitivity $a$ and the index of a starting platform where the robot can be placed. If there are multiple starting platforms corresponding to the same minimum initial sensitivity, output any one of them。

5
1
3 7 4 2 5

4 3

10
2
5 1 2 3
1 2 3 4 5

653 1

Hint

Sample explanation:

In the second example, the distance array is $[1, 2, 3, 4, 5, 18, 45, 112, 273, 662]$。

Compute the values of $d_6$ to $d_{10}$ using the formula:

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

This problem uses bundled testdata。

For $100\%$ of the data, $3 \le n \le 10^7$. When $f = 1$, $1 \le d_i \le 10^9$; when $f = 2$, $2 \le m \le \min(n, 10^5)$, $0 \le x, y, z \le 10^9$, and $1 \le c_i \le 10^9$。

Note: the algorithm tags of this problem refer to the methods used in the official solution.

Translated by ChatGPT 5