Задача 1. Чемпионат по устному счету ≡

Условие

Председатель жюри чемпионата по устному счету !A !B !C придумал новое задание для участников чемпионата. Исходно на доске выписывается n целых чисел: a₁, a₂, …, a_n. После этого участник должен выполнять команды двух типов:

1. Стереть i-е число с доски и записать вместо него число x. То есть, если на доске были записаны числа a₁, a₂, …, a_n,~ то после выполнения команды числа будут равны: a₁, …, a_i − 1, x, a_i + 1, …, a_n.

2. Циклически сдвинуть последовательность чисел на k вправо. То есть, если на доске были записаны числа a₁, a₂, …, a_n, то после выполнения команды числа будут равны: a_{n − k + 1}, a_{n − k + 2}, …, a_n, a₁, a₂, …, a_n − k.

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

Формат входных данных

В первой строке записано целое число n — количество чисел, изначально записанных на доске (2 ≤ n ≤ 10⁵).

Во второй строке через пробел записаны n целых чисел: a₁, a₂, …, a_n — числа, изначально выписанные на доске ( − 10⁹ ≤ a_i ≤ 10⁹).

В третьей строке записано целое число q — количество команд, которые необходимо выполнить (1 ≤ q ≤ 10⁵).

В каждой из следующих q строк записана очередная команда в следующем формате:

• 1 i x — это означает, что участник должен заменить i-е число последовательности на число x (1 ≤ i ≤ n;  − 10⁹ ≤ x ≤ 10⁹).

• 2 k — это означает, что участник должен циклически сдвинуть последовательность чисел на k вправо (1 ≤ k < n).

Формат выходных данных

В качестве ответа выведите q строк, в каждой из которых записано одно целое число.

В i-й строке должна быть записана сумма чисел на доске после выполнения первых i команд.

Обратите внимание, что ответ может быть достаточно большим и для его хранения потребуется 64-битный тип данных, int64 в паскале, long long в C++, long в Java.

Ограничения

2 ≤ n ≤ 10⁵

 − 10⁹ ≤ a_i ≤ 10⁹

1 ≤ q ≤ 10⁵

1 ≤ i ≤ n;  − 10⁹ ≤ x ≤ 10⁹

1 ≤ k < n

Система оценки

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

Замечание

Рассмотрим пример из условия. Изначально последовательность записанных на доске чисел равна: 4, 1, 2, 1, 5, 3.

После первой команды последовательность циклически сдвигается на 3 элемента вправо. Новая последовательность: 1, 5, 3, 4, 1, 2. Сумма чисел равна: 1 + 5 + 3 + 4 + 1 + 2 = 16.

После второй команды необходимо заменить третий элемент последовательности на число 10. Новая последовательность: 1, 5, 10, 4, 1, 2. Сумма чисел равна: 1 + 5 + 10 + 4 + 1 + 2 = 23.

После третьей команды заменить четвертый элемент на число 4. Так как четвертый элемент уже равен 4, последовательность не изменяется. Сумма чисел также равна 23.

После четвертой команды последовательность циклически сдвигается на 1: 2, 1, 5, 10, 4, 1. Сумма чисел не изменилась.

Наконец, после пятой команды последовательность становится равна:  − 10, 1, 5, 10, 4, 1. Сумма чисел в итоговой последовательности равна  − 10 + 1 + 5 + 10 + 4 + 1 = 11.

Примеры тестов

6
4 1 2 1 5 3
5
2 3
1 3 10
1 4 4
2 1
1 1 -10

16
23
23
23
11

3
1000000000 1000000000 1000000000
3
1 2 999999999
2 2
1 2 999999999

2999999999
2999999999
2999999998

Задача 2. Прыгающий робот ≡

Условие

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

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом a. Робот может перепрыгнуть с платформы i на платформу i + 1, если a ≥ d_i. Аналогично, прыжок с n-й платформы на 1-ю возможен, если a ≥ d_n. При этом после каждого прыжка ловкость робота увеличивается на~1.

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

Формат входных данных

На первой строке ввода находится число n (3 ≤ n ≤ 10⁷).

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

Если f = 1, то на третьей строке находятся n целых чисел d₁, d₂, …, d_n (1 ≤ d_i ≤ 10⁹).

Если f = 2, то на третьей строке находится число m (2 ≤ m ≤ min(n, 10⁵)) и три целых числа x, y и z (0 ≤ x, y, z ≤ 10⁹). На четвертой строке находятся m целых чисел c₁, c₂, …, c_m (1 ≤ c_i ≤ 10⁹). Значения d_i вычисляются по следующим формулам.

Если 1 ≤ i ≤ m, то d_i = c_i.

Если m + 1 ≤ i ≤ n, то d_i = ((x ⋅ d_i − 2 + y ⋅ d_i − 1 + z) mod 10⁹) + 1.

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

Формат выходных данных

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

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

Ограничения

Система оценки

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

Пояснение к примеру

Во втором примере массив расстояний между платформами равен [1, 2, 3, 4, 5, 18, 45, 112, 273, 662]. Значения от d₆ до d₁₀ вычисляются по формулам:

d₆ = ((1 ⋅ d₄ + 2 ⋅ d₅ + 3) mod 10⁹) + 1 = ((1 ⋅ 4 + 2 ⋅ 5 + 3) mod 10⁹) + 1 = 18

d₇ = ((1 ⋅ d₅ + 2 ⋅ d₆ + 3) mod 10⁹) + 1 = ((1 ⋅ 5 + 2 ⋅ 18 + 3) mod 10⁹) + 1 = 45

d₈ = ((1 ⋅ d₆ + 2 ⋅ d₇ + 3) mod 10⁹) + 1 = ((1 ⋅ 18 + 2 ⋅ 45 + 3) mod 10⁹) + 1 = 112

d₉ = ((1 ⋅ d₇ + 2 ⋅ d₈ + 3) mod 10⁹) + 1 = ((1 ⋅ 45 + 2 ⋅ 112 + 3) mod 10⁹) + 1 = 273

d₁₀ = ((1 ⋅ d₈ + 2 ⋅ d₉ + 3) mod 10⁹) + 1 = ((1 ⋅ 112 + 2 ⋅ 273 + 3) mod 10⁹) + 1 = 662

Примеры тестов

5
1
3 7 4 2 5

4 3

10
2
5 1 2 3
1 2 3 4 5

653 1

Задача 3. Треугольная головоломка ≡

Условие

Головоломка состоит из n треугольников. Чтобы решить головоломку, необходимо выбрать из них четыре треугольника и собрать из них большой треугольник по следующей схеме:

Треугольники не должны пересекаться, в объединении они должны давать треугольник. Ровно по одному из выбранных треугольников должны находиться в углах, а один треугольник должен располагаться в центре.

Треугольники лежат на столе, их можно свободно вращать и двигать, но нельзя зеркально отражать.

Формат входных данных

В первой строке дано одно целое число t — номер теста.

В второй строке дано одно целое число n — количество треугольников в головоломке (4 ≤ n ≤ 30).

В следующих n строках дано описание треугольников. Один треугольник описывается координатами трех своих углов, данных в порядке обхода треугольника против часовой стрелки. Все координаты по модулю не превышают 10⁵. Гарантируется, что треугольники не являются вырожденными. В исходном расположении треугольники могут пересекаться.

Формат выходных данных

В первой строке выведите одно целое число — количество наборов из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме.

В следующих строках выведите наборы. Каждый набор задается номерами треугольников, которые в него входят. Треугольники внутри набора можно выводить в любом порядке. Наборы можно выводить в любом порядке.

Ограничения

Система оценки

В этой задаче потестовая оценка. Каждый тест оценивается независимо и стоит 5 баллов.

Тесты удовлетворяют следующим ограничениям:

Пояснение к примеру

В первом примере из данных четырех треугольников можно собрать один. При этом треугольники не требуется вращать.

Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными 1. Из любых четырех треугольников можно собрать один.

Примеры тестов

1
4
0 0 6 2 1 2
0 0 5 0 6 3
0 0 3 1 1 3
0 0 6 3 3 6

1
1 2 3 4 

2
6
0 0 1 0 1 1
0 1 0 0 1 0
-1 0 0 0 0 1
1 1 0 1 1 0
-1 0 0 -1 0 0
0 0 1 1 0 1

15
1 2 3 4 
1 2 3 5 
1 2 3 6 
1 2 4 5 
1 2 4 6 
1 2 5 6 
1 3 4 5 
1 3 4 6 
1 3 5 6 
1 4 5 6 
2 3 4 5 
2 3 4 6 
2 3 5 6 
2 4 5 6 
3 4 5 6 

Задача 4. Массивы-палиндромы ≡

Условие

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: A = [a₁, a₂, …, a_n] длины n и B = [b₁, b₂, …, b_m] длины m.

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как A′ и B′, а их длину как k. Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как C = [c₁, c₂, …, c_k].

Пусть, например, n = 5, A = [4, 3, 3, 2, 1], m = 6, B = [4, 1, 5, 1, 3, 2], от массива A отбрасывается первый и последний элемент, от массива B три первых. После этого массивы имеют вид A′ = [3, 3, 2], B′ = [1, 3, 2], результат их поэлементного суммирования C = [4, 6, 4].

Задача Кая заключается в том, чтобы получать такие C, которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех i числа на позициях i и k − i + 1 совпадают.

Помогите Каю понять, какой максимальный по длине массив-палиндром он может получить в результате эксперимента.

Формат входных данных

В первой строке ввода даны два целых числа n и m — количество элементов в первом и во втором массиве, соответственно (1 ⩽ n, m ⩽ 100 000).

Во второй строке ввода даны n целых чисел a_i — массив A (1 ⩽ a_i ⩽ 100).

В третьей строке ввода даны m целых чисел b_j — массив B (1 ⩽ b_j ⩽ 100).

Формат выходных данных

Выведите единственное целое число — максимальное k, что Кай в результате эксперимента может получить массив-палиндром длины k.

Ограничения

1 ⩽ n, m ⩽ 100 000

1 ⩽ a_i ⩽ 100

1 ⩽ b_j ⩽ 100

Система оценки

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

Примеры тестов

5 6
4 3 3 2 1
4 1 5 1 3 2

3