Problem Background

Translated from ROIR 2022 D1T2.

A company is developing a jumping robot. To test the robot, they have set up a circular route consisting of $n$ special platforms on a polygonal platform, 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$ (assuming the edges of lengths $d_1, d_2, \dots, d_n$ can form an $n$-sided polygon).

The robot is equipped with artificial intelligence and learns to jump farther during the test. At any moment, the robot's sensitivity is represented by an integer $a$. 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 a 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 starting sensitivity of the robot and which platform to use as the starting platform.

Input Format

The first line contains an integer $n$.

The second line contains an integer $f$.

• If $f = 1$, the third line contains $n$ integers $d_1, d_2, \dots, d_n$, as described in the problem background.
• If $f = 2$, 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$. The distance values $d_i$ are calculated according to the following formula:
• 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 starting sensitivity $a$ and the starting platform number where the robot can be placed. If there are multiple starting platforms corresponding to the minimum starting sensitivity, you can output any one.

Sample Input and Output

Sample Input #1

5
1
3 7 4 2 5

Sample Output #1

4 3

Sample Input #2

10
2
5 1 2 3
1 2 3 4 5

Sample Output #2

653 1

Notes

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

The values for $d_6$ to $d_{10}$ are calculated according to the formula:

• $d_6 = ((1 \cdot d_4 + 2 \cdot d_5 + 3) \mod 10^9) + 1 = ((1 \cdot 4 + 2 \cdot 5 + 3) \mod 10^9) + 1 = 18$;
• $d_7 = ((1 \cdot d_5 + 2 \cdot d_6 + 3) \mod 10^9) + 1 = ((1 \cdot 5 + 2 \cdot 18 + 3) \mod 10^9) + 1 = 45$;
• $d_8 = ((1 \cdot d_6 + 2 \cdot d_7 + 3) \mod 10^9) + 1 = ((1 \cdot 18 + 2 \cdot 45 + 3) \mod 10^9) + 1 = 112$;
• $d_9 = ((1 \cdot d_7 + 2 \cdot d_8 + 3) \mod 10^9) + 1 = ((1 \cdot 45 + 2 \cdot 112 + 3) \mod 10^9) + 1 = 273$;
• $d_{10} = ((1 \cdot d_8 + 2 \cdot d_9 + 3) \mod 10^9) + 1 = ((1 \cdot 112 + 2 \cdot 273 + 3) \mod 10^9) + 1 = 662$.

This problem uses bundled testing.

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

Note: The algorithm tags for this problem are based on the solutions used in the official problem solution.

见题面 Input 部分

见题面 Output 部分