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

Вам дан массив \(V\) длины \(n\), и вы хотите уметь осуществлять над ним следующие операции:

1) get(\(a\), \(b\)) - узнать наибольший общий делитель чисел на отрезке от \(a\) до \(b\).

2) update(\(a\), \(b\), \(k\)) - для всех \(j\) от \(a\) до \(b\) увеличить \(j\)-е число на \(k \cdot (j - a + 1)\), т.е.

\(V_a += k\)

\(V_{a+1} += 2 \cdot k\)

...

\(V_b += (b - a + 1) \cdot k\)

У Элли есть \(N\) овец на пастбище. У неё также есть \(K\) гончих собак, которые охраняют овец от волков. Опасность для каждой овцы можно вычислить как расстояние до ближайшей собаки - чем оно меньше, тем лучше. Опасность для стада можно вычислить как сумму этих расстояний для каждой овцы. Мы считаем пастбище плоской поверхностью, а овец - точками на плоскости.

Элли задаётся вопросом, как расположить своих собак (которые также являются точками на плоскости), чтобы сумма минимальных расстояний от каждой овцы до ближайшей собаки была как можно меньше. Другими словами, вам даны \(N\) точек, и вам следует разместить \(K\) новых точек таким образом, чтобы сумма минимальных расстояний от каждой из заданных точек до ближайшей новой была как можно меньше. Напишите программу для решения этой задачи.

Мислав и Мирко разработали новую игру под названием повороты.

Сначала Мирко выбирает последовательность чисел длины \(n\) и число \(k\) и разбивает последовательность на секции, каждая из которых содержит \(k\) чисел (\(n\) делится на \(k\)). Первая секция содержит первые \(k\) позиций в последовательности, вторая секция содержит последующие \(k\) позиций в последовательности и так далее.

После этого Мирко начинает применять различные операции на данной последовательности. Есть два типа операций:

1. Совершить циклический сдвиг элементов последовательности чисел в каждой секции на \(x\) влево или вправо.

2. Совершить циклический сдвиг элементов последовательности чисел целиком на \(x\) влево или вправо.

Заметим, что операция типа 2 может изменить то, к какой секции принадлежит какое число.

После применения всех операций, Мирко сообщает Миславу получившуюся последовательность и применённые операции. Задача Мислава заключается в том, чтобы восстановить исходную последовательность. Он попросил вас о помощи.

Недавно в Байтландии изобрели Битовый Поляризационный Магнит. Если его применить, каждая дорога в Байтландии станет односторонней. Это будет очень плохо, ведь в Байтландии дороги образуют дерево — от каждого города до каждого ровно один путь. В зависимости от того, в какую сторону окажется ориентирована каждая дорога, различные города станут недостижимы друг из друга. Теперь ученые решили выяснить, насколько плохо будет жить в Байтландии, если применить БПМ. Определите минимальное и максимальное количество пар городов, что из первого по прежнему можно будет добраться до другого после применения магнита.

Поздравляем! Вас наняли управляющим одного крупного завода по производству чего-то очень важного. На вашем заводе есть \(n\) рабочих и \(n\) станков. Каждый рабочий умеет работать на каких-то станках, а на каких-то не умеет. К счастью, вы можете отправить какого-то рабочего на курсы повышения квалификации, чтобы он научился работать на каком-то станке, заплатив за это 1 тугрик. Нет никаких ограничений по тому, кого и сколько раз отправлять на курсы. У ваших работников также очень хорошая память, поэтому если они умели или научились работать на каком-то станке, то уже никогда не забудут, как это делать.

Но не все так радужно. Из-за кризиса сократили всех других менеджеров, поэтому рабочие сами определяют, за каким станком им работать в определенный день. Рабочие могут прийти на работу в случайном порядке. Когда рабочий пришел на работу он может выбрать любой еще не занятый станок, на котором умеет работать, и сядет за него. Если же такого не нашлось, то он расстроится и уйдет домой, а ваш завод понесет убытки. Так, если у вас было два рабочих, первый из которых умел работать на 1 и 2 станке, а второй только на первом, то если первый пришел на работу раньше и занял первый станок, то ваш завод понесет убытки.

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