У вас в распоряжении табло размера n на m пикселей. Каждый пиксель может быть либо включён, либо выключен. Табло будет использоваться для отображения стрелок, указывающих направление движения. Всего есть четыре направления: вверх, вниз, влево и вправо.

Рассмотрим как устроена стрелка, указывающая вверх: вертикальный отрезок высотой в b пикселей, из которого сверху вниз под углом в 45 градусов, выходят два отрезка из a пикселей. Стрелки для остальных направлений можно получить поворотами на 90 градусов.

Например, так выглядят стрелки для всех направлений с параметрами a = 3 и b = 7

При этом, параметры стрелки должны обладать следующими ограничениями:

 — 2a ≤ b;

 — 2 ≤ a.

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

Для каждого направления вам нужно посчитать количество различных стрелок, которые можно отобразить на данном табло. Две стрелки с параметрами (a₁, b₁) и (a₂, b₂) считаются одинаковыми, если a₁ = a₂ и b₁ = b₂.

У Васи есть четыре спички, из которых он хочет выложить четырёхугольник.

Больше всего он любит квадраты и не против увидеть прямоугольник. Остальные фигуры он считает безобразными.

Выясните, какую лучшую фигуру Вася может сделать. Если это квадрат, то выведите «square», если прямоугольник, то «rectangle». Иначе следует вывести «ugly».

Земля наконец-то установила контакт с инопланетной цивилизацией, которая посылает сообщения через радиосигнал. Началось всё с объёмного сообщения, в котором объяснялись фундаментальные вещи логики, математики, физики и других наук, например, что такое целое число.

Позже было разъяснено, что такое перестановка — последовательность P из N целых различных чисел, каждое из которых лежит в диапазоне от 1 до N. А также, что такое инверсии в последовательности a — это количество таких i и j, что 1 ≤ i < j ≤ N и a_i > a_j.

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

Например, пусть была загадана перестановка (3, 6, 1, 4, 5, 2) и нас интересует ответ на набор чисел {2, 3, 4}. Если оставить только эти числа, выйдет (3, 4, 2), и ответом будет 2 — именно столько инверсий содержится в новой последовательности.

Обратите внимание, что перестановка не меняется после ответа на вопрос.

К сожалению, общение в космосе является очень утомительным по времени занятием, особенно когда собеседник находится в системе Веги, что почти в 26-и световых годах от нас. Поэтому суммарное количество выбранных чисел для вопросов ограничено в 40 000.

Помогите нашей цивилизации пройти экзамен, отгадайте перестановку!

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

В начале вам на ввод подаётся целое число N — размер перестановки (1 ≤ N ≤ 1000).

Далее ваша программа общается с программой жюри. Вы можете выводить запрос на количество инверсий в формате «? k t₁ t₂ ... t_k», где t_i и есть выбранные числа. Каждый такой запрос должен быть в отдельной строке и заканчиваться очисткой буфера вывода.

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

Если вы считаете, что отгадали перестановку, следует вывести её в отдельной строке в формате «! P₁ P₂ ... P_N», разделяя числа пробелами. После этого ваша программа должна немедленно завершиться.

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

Перед вами инструкция по созданию шедевра, выданная такой нейросетью. Она задана как последовательность символов, означающих, как нужно двигать кистью: «U» — движение вверх, «D» — вниз, «L» — влево, «R» — вправо. Каждое движение должно переместить кисть на одну единицу измерения. Мы будем считать, что рисование шедевра происходит на обычном клетчатом листе бумаги.

Вам нужно реализовать программу, которая нарисует по инструкции картину, и выведет её в минимально возможном прямоугольнике.

В начале урока физической культуры n школьников выстроились в ряд. Нумерация происходит от 1 до n, начиная слева.

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

Например, если n = 5 и m = 3, то вам необходимо добиться расстановки 4 5 1 2 3.

При этом, просто перейти в конец детям будет скучно. Вы можете произнести команду, характеризующуюся двумя числами a и b — текущими номерами детей в ряду. После этого дети с этими номерами выходят из ряда и меняются местами.

Чтобы не затягивать урок, Вам необходимо выдать не более n команд.

Ефим и Серафим целый день играли в ним. Ефим всегда выигрывал, поэтому Серафиму надоело играть с ним и он решил изменить игру.

Есть одна кучка из n камней.

Игроки ходят по очереди. Проигрывает тот, кто возьмёт последний камень.

На первом ходу игрок может взять любое количество камней от 1 до n.

На каждом последующем ходу игрок ограничен в своём ходе относительно P — сколько камней было взято другим игроком на предыдущем ходу. На текущем ходу игрок может взять количество камней S такое, что оно равно P, либо такое, что чётности P и S различаются. Например, если на предыдущем ходу было взято 5 камней, то сейчас можно взять либо также 5, либо любое чётное положительное количество.

Игрок обязан ходить, если у него есть допустимый ход. Если же допустимых ходов нет, объявляется ничья. На каждом ходу нужно брать хотя бы один камень.

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

Определите для заданного n кто выиграет в игре.

Оксаночке задали домашнее задание по теме системы счисления.

Ей нужно выписать все числа от 0 до 3^M - 1 так, чтобы соседние числа различались ровно в одной цифре, если их рассмотреть в троичной системе счисления.

Троичная запись числа при необходимости дополняется ведущими нулями до длины M.

Сможете ли Вы сделать тоже самое для данного M?