Мы создали бесконечный кроссворд, взяв прямоугольник размера \(\)\(N \times M\)\(\), заполненный буквами и замостили им бесконечную плоскость. Например, прямоугольник

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

Вы знаете, в чём разница между отелем и мотелем? Верно, разница в количестве мух, которые там живут. Норман – владелец одного из самых популярных мотелей в Америке,но его мать хочет, чтобы он стал отелем. Именно поэтому Норман купил мухобойку ( мухобойка – инструмент для отпугивания или прихлопывания мух. Может представлять собой как пластиковое или резиновое изделие на длинной ручке, так и пучок волос или листьев). Мухобойка представляет из себя многоугольник из \(\)\(K\)\(\) рёбер.

Желая угодить своей матери, Норман встал у окна, на котором сидели \(\)\(N\)\(\) мух. Так как норманн – пацифист, он не может причинить вред другому живому существу, в том числе, мухе. Именно поэтому ему интересно количество способов ударить по окну мухобойкой, не задев ни одной мухи.

Окно представляет из собой прямоугольник с левой нижней вершиной в точке \(\)\((0, 0)\)\(\) и правой верхней – в точке \(\)\((X_p, Y_p)\)\(\). После того как Норман ударит по окну все вершины многоугольника должны лежать в точках с целыми координатами, а мухобойка должна полностью лежать внутри прямоугольника окна. Норману интересно, сколькими способами он может ударить по окну, не убив ни единой мухи.

Рассмотрим следующую операцию, определённую на целых положительных числах. Операция состоит в умножении числа \(q\) на простое число \(p\), либо в делении числа \(q\) на простое число \(p\), если \(q\) делится на \(p\) без остатка. Назовем расстоянием между числами \(a\) и \(b\) минимальное количество операций, необходимое для того чтобы получить из числа \(a\) число \(b\). Обозначим расстояние как \(d(a, b)\).

Дана последовательность из \(n\) положительных чисел \(a_1, a_2, ... a_n\). Для каждого индекса \(i\) (\( 1 \le i \le n\)) необходимо найти индекс \(j\), такой что \(1 \le j \le n\) и \(i \ne j\), и что \(d(a_i, a_j)\) минимально.

Байтазар планирует заняться производством солнечных панелей. Он получил \(n\) заказов, каждый заказ характеризуется минимальной \(w_{min}\) и максимальной \(w_{max}\) шириной солнечной панели, а также минимальной \(l_{min}\) и максимальной \(l_{max}\) длиной солнечной панели. Выполняя заказ, Байтзар может изготовить солнечную панель любого размера \(a \times b\), такого что \(w_{min} \le a \le w_{max}, l_{min} \le b \le l_{max}\). Солнечная панель состоит из квадратных ячеек. Ячейка может иметь любой размер \(c \times c\), где \(c\) — целое число. Байтазар хотел бы использовать для каждого заказа как можно большие по размеру ячейки. Помогите ему найти для каждого заказа максимальное \(c\), такое что он сможет выполнить заказ, используя ячейки \(c \times c\).

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

Вам дан массив \(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\)