Железная дорога Флатландии представляет собой прямую, вдоль которой расположены \(n\) станций. Будем называть участок железной дороги от некоторой станции до следующей перегоном.

Поезд следует от станции 1 до станции \(n\), делая остановку на каждой станции. В поезде \(k\) мест, пронумерованных от 1 до \(k\). На поезд продаются билеты, каждый билет характеризуется тремя числами: \(s\), \(t\) и \(a\). Такой билет позволяет проехать от станции \(s\) до станции \(t\) на месте \(a\).

Вася планирует в один из дней летних каникул проехать на поезде от одной станции до другой. Он выяснил, что на поезд в этот день уже продано \(m\) билетов, и возможно уже нет мест, свободных на всех перегонах между интересующими его станциями. Билет от одной станции до другой на определенное место можно купить, только если это место свободно на всех перегонах между этими станциями.

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

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

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

Во владениях короля Флатландии находится прямая дорога длиной \(n\) километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.

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

• каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры \(a \times a, b \times b\) и \(c \times c\);
• стороны квадратов должны полностью покрывать дорогу: величина a + b + c должна быть равна \(n\);
• участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство \(a < b < c\);
• суммарная площадь участков \(a^2 + b^2+ c^2\) должна быть минимальна.

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй — \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).

Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в \(k\) раз.

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

Требуется написать программу, которая по числу \(k\) и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, …, a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3 = a_2 + a_4, …, a_{n-1} = a_{n-2} + a_n\). Например, последовательность \([1, 2, 1, –1]\) является гармоничной, поскольку \(2 = 1 + 1\), и \(1 = 2 + (–1)\).

Рассмотрим последовательности равной длины: \(A = [a_1, a_2, …, a_n]\) и \(B = [b_1, b_2, …, b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A, B) = |a_1 – b_1| + |a_2 – b_2| + … + |a_n – b_n|\). Например, \(d([1, 2 ,1, –1], [1, 2, 0, 0]) = |1 – 1| + |2 – 2| + |1 – 0| + |–1 – 0| = 0 + 0 + 1 + 1 = 2.\)

В конце лекции профессор написал на доске последовательность из \(n\) целых чисел \(B = [b_1, b_2, …, b_n]\) и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A = [a_1, a_2, …, a_n]\), такую, что \(d\)(\(A\), \(B\)) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A, B)\).

Требуется написать программу, которая по заданной последовательности \(B\) определяет, на каком минимальном расстоянии от последовательности \(B\) найдется гармоничная последовательность \(A\).