题目描述

译自 ROI Regional 2022 Day1 T2. Прыгающий робот

Flatland Dynamics 公司正在开发一款跳跃机器人。为了测试这款机器人，他们在一个测试场地上设置了一个由 $n$ 个特殊平台组成的环形路线，这些平台从 $1$ 到 $n$ 依次编号。第 $i$ 个平台和第 $i+1$ 个平台之间的距离为 $d_i$，第 $n$ 个平台和第 $1$ 个平台之间的距离为 $d_n$。

机器人配备了人工智能，并在测试过程中学习跳得更远。在任何时候，机器人的“灵活度”用一个整数 $a$ 来表示。机器人可以从第 $i$ 个平台跳到第 $i+1$ 个平台，如果 $a \ge d_i$。同样地，如果 $a \ge d_n$，机器人可以从第 $n$ 个平台跳到第 $1$ 个平台。每次跳跃后，机器人的灵活度会增加 $1$。

开发人员会选择一个平台作为起点。如果机器人能够从当前平台开始，连续跳跃 $n$ 次，完成一个完整的环并回到起点，他们就认为实验成功。开发人员需要找出机器人初始灵活度的最小值，以及从哪个平台开始跳跃才能成功完成实验。

输入格式

第一行包含一个整数 $n$ $(3 \le n \le 10^7)$。

第二行包含一个整数 $f$，描述距离数组的格式。

• 如果 $f = 1$，第三行包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$ $(1 \le d_i \le 10^9)$。

• 如果 $f = 2$，第三行包含一个整数 $m$ $(2 \le m \le \min(n, 10^5))$ 和三个整数 $x, y, z$ $(0 \le x, y, z \le 10^9)$。第四行包含 $m$ 个整数 $c_1, c_2, \ldots, c_m$ $(1 \le c_i \le 10^9)$。距离 $d_i$ 按以下公式计算：

  • 如果 $1 \le i \le m$，则 $d_i = c_i$。
  • 如果 $m + 1 \le i \le n$，则 $d_i = \left((x \cdot d_{i-2} + y \cdot d_{i-1} + z) \bmod 10^9\right) + 1$。

  这里，$\bmod$ 表示取模运算，在 C++、Java 和 Python 中用符号 % 表示。

输出格式

输出两个整数：最小的初始灵活度 $a$ 和机器人应该开始跳跃的起始平台编号。如果有多个可能的起始平台，可以输出其中任意一个。

5
1
3 7 4 2 5

4 3

10
2
5 1 2 3
1 2 3 4 5

653 1

在样例 2 中，平台之间的距离数组为 $[1, 2, 3, 4, 5, 18, 45, 112, 273, 662]$。从 $d_6$ 到 $d_{10}$ 的值按以下公式计算：

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

数据范围与提示

详细子任务附加限制及分值如下表所示。