Студент Петя устал от однотипных окон. Он хочет сделать окно таким образом, чтобы оно отвечало его стандартам красоты. Высота окна в комнате Пети равна $$$H$$$, а ширина равна $$$W$$$.

Петя хочет разделить окно вертикальной створкой на две части (левую и правую) так, чтобы ширина левой части была равна целому числу $$$A$$$, а ширина правой части была равна $$$W - A$$$.

После этого он хочет разделить правую часть окна горизонтальной створкой на верхнюю и нижнюю части так, чтобы высота верхней части была равна целому числу $$$B$$$, а высота нижней части была равна $$$H - B$$$.

Пусть $$$S_1$$$, $$$S_2$$$ и $$$S_3$$$ — площади получившихся трех частей, на которые створки разделили окно. Петя считает красоту окна равной числу $$$K = \min(S_1, S_2, S_3)$$$.

Зная размеры окна $$$H$$$ и $$$W$$$ найдите максимально возможное значение красоты $$$K$$$, при условии, что в качестве размеров $$$A$$$ и $$$B$$$ можно выбрать любые целые числа, которые удовлетворяют неравенствам $$$1 \le A \lt W$$$ и $$$1 \le B \lt H$$$.

Студент Саша любит решать в уме геометрические задачи. Однажды он увидел в магазине мед в сотах и придумал следующую задачу.

На координатной плоскости нарисованы два правильных шестиугольника с длиной стороны равной $$$1$$$. Каждый из шестиугольников расположен таким образом, что две его стороны параллельны оси $$$Y$$$, а нижняя вершина располагается в заданной точке плоскости с целочисленными координатами. Требуется найти площадь пересечения нарисованных шестиугольников.

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

Саша округляет числа по следующим правилам. Если дробная часть числа меньше $$$0.5$$$, то Саша округляет число в меньшую сторону, а иначе в большую сторону. Например, числа $$$1$$$, $$$1.2$$$, $$$1.499999$$$ округляются до целого числа $$$1$$$, а числа $$$1.5$$$, $$$1.777$$$, $$$1.9991$$$ округляются до целого числа $$$2$$$.

Однажды студент МИСИС Анатолий сидел вечерком за компьютером и вел беседу с голосовым помощником от VK Марусей. Анатолий большой любитель программирования, поэтому разговор в итоге зашел о графах. От Маруси Анатолий узнал про деревья. А именно, граф из $$$n$$$ вершин является деревом, если он связный и у него $$$n - 1$$$ ребро. На этот момент Анатолий уже знал, что граф называют связным, когда между любой парой вершин этого графа существует как минимум один путь.

Этот разговор навел Анатолия на интересные мысли. Он представил себе граф из $$$n$$$ вершин, который является деревом. Далее он ввел обозначение $$$dist(a, b)$$$, которое обозначает кратчайшее расстояние между вершинами $$$a$$$ и $$$b$$$ в задуманном дереве. То есть $$$dist(a, b)$$$ — это наименьшее количество ребер, через которые необходимо пройти, чтобы из вершины $$$a$$$ попасть в вершину $$$b$$$. Затем Анатолий загадал число $$$m$$$ и определил, что в его графе $$$dist(a, b) \le m$$$ для всех пар $$$1 \le a, b \le n$$$, а также выполнено условие $$$dist(1, 2) = m$$$.

Позже Анатолий еще немного поговорил с Марусей о погоде и снова вернулся к размышлениям о задуманном дереве. На этот раз он задумался о далеких вершинах своего дерева. Вершина $$$v$$$ в дереве Анатолия называется далекой, если выполнены два условия $$$dist(1, v) = m$$$ и $$$dist(2, v) = m$$$.

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

У девочки Кати есть клетчатое поле размера $$$n \times m$$$. Любимая фигура Кати уголок — фигура из трех клеток, которая может быть получена из квадрата $$$2 \times 2$$$ удалением одной из клеток. Катя хочет разрезать имеющееся у нее поле на уголки. Но ее младший брат Женя решил вырезать ровно одну клетку поля так, чтобы у Кати не получилось разрезать оставшуюся часть поля на уголки.

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

Абитуриент Максим усиленно готовится к поступлению в МИСИС по олимпиаде. Поэтому он попросил своего учителя дать ему задачу для тренировки. Учитель знает, что Максим испытывает трудности с задачами, в которых нужно отвечать на запросы, поэтому дал ему именно такую задачу.

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

В этой задаче вам дан массив, состоящий из $$$n$$$ целых чисел.

Требуется обработать $$$q$$$ запросов двух типов. Каждый запрос состоит из двух целых чисел — типа запроса и номера элемента массива:

• $$$1$$$ $$$i$$$ — в ответ на запрос первого типа необходимо вывести значение наименьшего элемента $$$a_j$$$ такого, что $$$a_j \gt a_i$$$ и $$$j \gt i$$$.
• $$$2$$$ $$$i$$$ — после запроса второго типа необходимо выполнить операцию изменения: $$$a_i = -a_i$$$.

Студент МИСИС Роман пишет курсовую в лаборатории случайных последовательностей. Заведующий лабораторией дал Роману два числа $$$n$$$, $$$k$$$ и поручил сгенерировать случайную последовательность длины $$$n$$$. Каждый член этой последовательности является целым числом, которое выбирается с равной вероятностью из диапазона от $$$1$$$ до $$$k$$$ включительно.

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

Помогите Роману ответить на этот вопрос.

Дана таблица из $$$n$$$ строк и $$$m$$$ столбцов, заполненная строчными буквами латинского алфавита.

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

Следующие таблицы являются хорошими:

Следующие таблицы не являются хорошими:

Требуется найти количество хороших подтаблиц данной таблицы.

У Миши есть ориентированный граф из $$$n$$$ вершин. Из каждой вершины графа выходит ровно два ребра — синее и красное. Папа Миши увидел этот граф и придумал $$$q$$$ маршрутов.

Каждый маршрут задается номером начальной вершины $$$v$$$ и состоит из перемещений. Перемещения состоят из переходов и задаются строкой $$$s$$$.

Строка $$$s$$$ формируется по следующим правилам:

• Длина строки в точности равна $$$9$$$
• От $$$1$$$ до $$$8$$$ первых символов строки являются цифрами и задают количество перемещений — число $$$M$$$ (не имеет ведущих нулей).
• Оставшиеся позиции занимают символы «$$$R$$$» и «$$$B$$$», описывающие переходы в рамках одного перемещения — символ «$$$R$$$» задаёт переход по красному ребру, символ «$$$B$$$» задаёт переход по синему ребру.

Например, маршрут, начинающийся в вершине $$$529$$$ и состоящий из $$$79854$$$ перемещений, каждое из которых требует совершить переходы по синему-красному-красному-синему рёбрам, опишется следующим вводом:

• $$$529$$$ $$$79854BRRB$$$

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

Это интерактивная задача.

Студент Иван обожает игры, в которых нужно отгадывать числа.

В данный момент он играет на компьютере в игру, в которой нужно отгадать два загаданных числа $$$A$$$ и $$$B$$$, $$$(0 \le A, \ B \le 10^{9})$$$. В этой игре можно сделать запрос, который заключается в том, чтобы дать компьютеру число $$$X$$$, а в ответ получить значение выражения $$$(A \oplus X) + B$$$. Разрешается сделать не более пяти таких запросов, после чего игрок должен отгадать оба числа.

Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ — бинарная операция, действие которой эквивалентно применению логического исключающего ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если оба соответствующих бита операндов равны между собой, двоичный разряд результата равен $$$0$$$, в противном случае, двоичный разряд результата равен $$$1$$$.

Операция $$$\oplus$$$ существует во всех современных языках программирования, например, в языках Python, C++ и Java она обозначена как «$$$^\land$$$», а в Pascal — как «$$$\text{xor}$$$».

Для сброса буфера вывода (то есть для операции «flush») сразу после вывода нужно сделать:

• C++: endl одновременно и делает перевод строки, и «flush»;

  Другие варианты: cout.flush(), cout << flush.

• Java: System.out.println() одновременно и делает перевод строки, и «flush».

  Если вы используете не System.out, то используйте команду flush вашего потока вывода.

• Python: print одновременно и делает перевод строки, и «flush»;

  Напрямую можно сделать «flush» с помощью sys.stdout.flush() (требует import sys).

• Pascal: Выполните flush(output) после вывода через writeln.

Профессор Невзломайкин преподает криптографию в Берляндском институте безопасного информационного пространства «БИБИП». На одну из лекций профессор принёс целое число $$$n$$$, а также параметр $$$k$$$ — простое число, делящее $$$n$$$ нацело.

Профессор задал следующие определения:

• Конфигурация — перестановка $$$P$$$ длины $$$n$$$ (массив, в котором каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз).
• Ключ — перестановка $$$B$$$ длины $$$n$$$ такая, что остаток произведения $$$P_i \cdot B_i$$$ при делении на $$$k$$$ равен остатку числа $$$i$$$ при делении на $$$k$$$ $$$(1 \le i \le n)$$$.

Далее профессор дал главное определение: конфигурация $$$P$$$ является счастливой, если существует ровно $$$\displaystyle\left(\left(\frac{n}{k}\right)!\right)^k$$$ различных перестановок $$$B$$$, являющихся ключами к перестановке $$$P$$$.

Профессор пообещал поставить за семестр «отлично» первому студенту, который найдёт любую счастливую конфигурацию. Представьте, что вы студент «БИБИПа», который очень не хочет ночами готовиться к экзамену по криптографии — предъявите профессору Невзломайкину любую счастливую конфигурацию или сообщите, что для заданных $$$n$$$ и $$$k$$$ счастливой конфигурации не существует.