{"raw_statement":[{"iden":"background","content":"翻译自 [ROIR 2022 D1T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day1.pdf)。\n\n某公司正在开发一种跳跃机器人。为了测试机器人，他们在一个多边形平台上设置了一个由 $n$ 个特殊平台组成的环形路线，平台从 $1$ 到 $n$ 编号。第 $i$ 个平台与 $i+1$ 个平台之间的距离为 $d_i$，最后一个平台与第一个平台之间的距离为 $d_n$（假设长度分别为 $d_1,d_2,\\dots,d_n$ 的边可以组成一个 $n$ 边形）。\n\n机器人配备了人工智能，在测试过程中学习跳得更远。在任何时刻，机器人通过一个整数 $a$ 来表示它的灵敏度。如果 $a$ 大于等于 $d_i$，机器人可以从平台 $i$ 跳到平台 $i+1$；同样地，如果 $a$ 大于等于 $d_n$，机器人可以从最后一个平台跳到第一个平台。每次跳跃后，机器人的灵敏度增加 $1$。"},{"iden":"statement","content":"机器人的开发人员选择一个平台作为起始平台。如果机器人可以完成 $n$ 次跳跃，回到原来的平台，他们认为实验是成功的。开发人员需要确定机器人的最小起始灵敏度是多少，并选择哪个平台作为起始平台。"},{"iden":"input","content":"第一行包含一个整数 $n$。\n\n第二行包含一个整数 $f$。\n\n- 如果 $f = 1$，则第三行包含 $n$ 个整数 $d_1, d_2, \\dots , d_n$，意义见题目背景。\n- 如果 $f = 2$，则第三行包含一个整数 $m$，以及三个整数 $x,y,z$。第四行包含 $m$ 个整数 $c_1, c_2, \\dots , c_m$。此时距离值 $d_i$ 根据以下公式计算：\n   - 如果 $1 \\le i \\le m$，则 $d_i = c_i$。\n   - 如果 $m + 1 \\le i \\le n$，则 $d_i = ((x \\times d_{i−2} + y \\times d_{i−1} + z) \\bmod 10^9) + 1$。"},{"iden":"output","content":"输出两个整数，即最小允许的起始灵敏度 $a$ 和可用于放置机器人的起始平台编号。如果有多个最小起始灵敏度对应的起始平台，可以输出任意一个。"},{"iden":"note","content":"样例说明：\n\n在第二个示例中，距离数组为 $[1, 2, 3, 4, 5, 18, 45, 112, 273, 662]$。\n\n根据公式计算 $d_6$ 到 $d_{10}$ 的值：\n\n- $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$；\n- $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$；\n- $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$；\n- $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$；\n- $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$。\n\n本题使用捆绑测试。\n\n| 子任务 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $0$ | $15$ | $n\\le300,f=1,d\\le300$ |\n| $1$ | $17$ | $n\\le5000,f=2$ |\n| $2$ | $10$ | $n\\le100000,f=1$ 且保证从第一个平台开始跳是最佳选择 |\n| $3$ | $20$ | $n\\le100000,f=1$ |\n| $4$ | $5$ | $f=2$ 且保证从第一个平台开始跳是最佳选择 |\n| $5$ | $33$ | $f=2$ |\n\n对于 $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$。\n\n注：本题的算法标签部分参考了官方题解中用到的解法。"}],"translated_statement":null,"sample_group":[["5\n1\n3 7 4 2 5","4 3"],["10\n2\n5 1 2 3\n1 2 3 4 5","653 1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}