Прыгающий робот

Сложность: 37%

Компания Flatland Dynamics разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из nn специальных платформ, пронумерованных от 11 до nn. Расстояние между ii-й и i+1i+1-й платформой равно did_i, аналогично расстояние между nn-й и 11-й платформой равно dnd_n.

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью – целым числом aa. Робот может перепрыгнуть с платформы ii на платформу i+1i+1, если adia \ge d_i. Аналогично, прыжок с nn-й платформы на 11-ю возможен, если adna \ge d_n. При этом после каждого прыжка ловкость робота увеличивается на 11.

Разработчики робота выбирают одну из платформ в качестве стартовой. Они считают эксперимент удачным, если робот может, совершив nn прыжков от текущей платформы к следующей, завершить полный круг и вернуться на ту же платформу. Разработчикам необходимо выяснить, для какого минимального значения начальной ловкости робота им удастся провести эксперимент и с какой платформы роботу следует начать прыжки.

Входные данные

На первой строке ввода находится число nn (3n1073 \le n \le 10^7).

Вторая строка содержит одно целое число ff, которое описывает формат, в котором задан массив расстояний между платформами.

Если f=1f = 1, то на третьей строке находятся nn целых чисел d1,d2,,dnd_1, d_2, \ldots, d_n (1di1091 \le d_i \le 10^{9}).

Если f=2f = 2, то на третьей строке находится число mm (2mmin(n,105))\left(2 \le m \le \min(n, 10^5)\right) и три целых числа xx, yy и zz (0x,y,z1090 \le x, y, z \le 10^9). На четвертой строке находятся mm целых чисел c1,c2,,cmc_1, c_2, \ldots, c_m (1ci1091 \le c_i \le 10^9). Значения did_i вычисляются по следующим формулам.

Если 1im1 \le i \le m, то di=cid_i = c_i.

Если m+1inm + 1 \le i \le n, то di=((xdi2+ydi1+z)mod109)+1d_i = \left((x\cdot d_{i-2} + y\cdot d_{i-1} + z)\bmod 10^9\right) + 1.

Здесь mod\bmod означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом %.

Выходные данные

Требуется вывести два целых числа: минимальную допустимую начальную ловкость aa и номер стартовой платформы, на которую можно разместить робота, чтобы успешно провести эксперимент.

Если возможных стартовых платформ для минимальной начальной ловкости несколько, можно вывести любую из них.

Подзадачи

баллынеобх. подзадачиограничения
0

0

-

Тесты из условия

1

15

-

n300n \le 300, f=1f = 1, di300d_i ⩽ 300

2

17

1

n5000n ⩽ 5000, f=1f = 1,

3

10

-

n100000n ⩽ 100 000, f=1f = 1, гарантируется, что оптимально начать с первой платформы

4

20

1, 2, 3

n100000n \le 100 000, f=1f = 1

5

5

3

f=2f = 2, гарантируется, что оптимально начать с первой платформы

6

33

1, 2, 3, 4, 5

f=2f = 2

STDINSTDOUT
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][1, 2, 3, 4, 5, 18, 45, 112, 273, 662]. Значения от d6d_6 до d10d_{10} вычисляются по формулам:

d6=((1d4+2d5+3)mod109)+1=((14+25+3)mod109)+1=18d_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

d7=((1d5+2d6+3)mod109)+1=((15+218+3)mod109)+1=45d_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

d8=((1d6+2d7+3)mod109)+1=((118+245+3)mod109)+1=112d_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

d9=((1d7+2d8+3)mod109)+1=((145+2112+3)mod109)+1=273d_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

d10=((1d8+2d9+3)mod109)+1=((1112+2273+3)mod109)+1=662d_{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