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

Вам дан массив \(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\) субмарин бороздят просторы океана. Они расположены в ряд с первой по \(N\)-ю, расстояние между соседними по горизонтали \(5 км\). Они плывут в одну сторону в этом же порядке (впереди - первая) с одинаковыми постоянными скоростями, каждая на своей глубине. Каждая может послать сигнал, который получит ближайшая (по евклидову расстоянию на плоскости) из плывущих сзади, которая расположена глубже лодки, посылающей сигнал, если такая есть, и никто больше.

Происходят 2 вида событий:

"Поменять две соседних субмарины местами" - в нем указывается число \(i\) - номер одной из них, другая имеет номер \(i+1\). Действие происходит мгновенно, субмарины остаются на своих же глубинах.

"Отправить сигнал" – каждая субмарина отправляет сигнал.

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

Генная инженерия это весело. Ученые собрали несколько ДНК и хотят создать из них что-то новое. Каждая ДНК может быть представлена в виде последовательности оснований \(A\), \(G\), \(T\), \(C\). Обозначим за \(DNA[a:b]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и заканчивающийся в индексе \(b\), и за \(DNA[a..]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и идущий до конца последовательности. Ученые хотят производить следующие операции над последовательностью ДНК:

• Операция скрещивания: ученые берут два ДНК \(DNA_1\) и \(DNA_2\) и числа \(k_1\) и \(k_2\). После этого они создают два новых ДНК: \(DNA_3 = DNA_1[1..k1] + DNA_2[k2+1..]\) и \(DNA_4 = DNA_2[1..k_2] + DNA_1[k_1+1..]\).
• Операция мутации – они берут ДНК, число \(k\) и одно из оснований. После этого они заменяют основание в позиции \(k\) выбранного ДНК на новое основание.
• Также иногда ученым интересно получать статистику о своих ДНК. Для этого они применяют операцию подсчёта – они берут ДНК и числа \(k_1\) и \(k_2\) (\(k_1 \le k_2\)). Они хотят узнавать количества оснований \(A\), \(G\), \(T\), \(C\) в \(DNA[k_1..k_2]\).

Исходные ДНК нумеруются от \(1\) до \(n\) где \(n\) - количество индексов. При создание новых ДНК они занимают два минимальных неиспользуемых натуральных индекса.

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

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

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

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

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

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

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