题目背景

翻译自 ROIR 2022 D1T2。

某公司正在开发一种跳跃机器人。为了测试机器人，他们在一个多边形平台上设置了一个由 $n$ 个特殊平台组成的环形路线，平台从 $1$ 到 $n$ 编号。第 $i$ 个平台与 $i+1$ 个平台之间的距离为 $d_i$，最后一个平台与第一个平台之间的距离为 $d_n$（假设长度分别为 $d_1,d_2,\dots,d_n$ 的边可以组成一个 $n$ 边形）。

机器人配备了人工智能，在测试过程中学习跳得更远。在任何时刻，机器人通过一个整数 $a$ 来表示它的灵敏度。如果 $a$ 大于等于 $d_i$，机器人可以从平台 $i$ 跳到平台 $i+1$；同样地，如果 $a$ 大于等于 $d_n$，机器人可以从最后一个平台跳到第一个平台。每次跳跃后，机器人的灵敏度增加 $1$。

题目描述

机器人的开发人员选择一个平台作为起始平台。如果机器人可以完成 $n$ 次跳跃，回到原来的平台，他们认为实验是成功的。开发人员需要确定机器人的最小起始灵敏度是多少，并选择哪个平台作为起始平台。

输入格式

第一行包含一个整数 $n$。

第二行包含一个整数 $f$。

• 如果 $f = 1$，则第三行包含 $n$ 个整数 $d_1, d_2, \dots , d_n$，意义见题目背景。
• 如果 $f = 2$，则第三行包含一个整数 $m$，以及三个整数 $x,y,z$。第四行包含 $m$ 个整数 $c_1, c_2, \dots , c_m$。此时距离值 $d_i$ 根据以下公式计算：
  • 如果 $1 \le i \le m$，则 $d_i = c_i$。
  • 如果 $m + 1 \le i \le n$，则 $d_i = ((x \times d_{i−2} + y \times d_{i−1} + z) \bmod 10^9) + 1$。

输出格式

输出两个整数，即最小允许的起始灵敏度 $a$ 和可用于放置机器人的起始平台编号。如果有多个最小起始灵敏度对应的起始平台，可以输出任意一个。

5
1
3 7 4 2 5

4 3

10
2
5 1 2 3
1 2 3 4 5

653 1

提示

样例说明：

在第二个示例中，距离数组为 $[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$。

本题使用捆绑测试。

对于 $100\%$ 的数据，$3 \le n \le 10^7$。当 $f=1$ 时 $1 \le d_i \le 10^9$，当 $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$。

注：本题的算法标签部分参考了官方题解中用到的解法。