Бойцовский клуб дебатов - необычный клуб во всех отношениях. Каждый из \(2^{n}\) его членов заполнил специальную анкету, содержащую \(n\) вопросов с бинарным ответом (да/нет) о своих взглядах. Ответы каждого человека могут быть представлены в виде последовательности из \(n\) бит, иначе говоря в виде числа от \(0\) до \(2^{n} - 1\).

Перечислим ещё несколько инетерсных фактов о бойцовском клубе дебатов.

• взгляды никаких двух членов клуба не совпадают, т. е. каждое из чисел от от \(0\) до \(2^{n} - 1\) встречается в числовых представлениях анкеты клуба
• ровно половина членов клуба мужчины, остальные - женщины (т. е. и мужчин, и женщин по \(2^{n - 1}\)) и они формируют \(2^{n - 1}\) разнополых пар
• два члена клуба считаются близкими по взглядам тогда, и только тогда когда у них в анкете отличается ответы ровно на один вопрос (иначе говоря, \(a_i \oplus b_i = 2^k\) для некоторого \(k\), где \(a_i\) и \(b_i\) - числа, кодирующие взгляды первого и второго человека соответственно)
• во время дебатов члены клуба сидят за круглым столом
• члены клуба хотят сидеть так, чтобы соеседями с одной стороны была его пара, с другой стороны, человек, близкий ему по взглядам

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

А именно, он знает, что в его городе живет ровно \(N\) человек и каждый житель живет в своем собственном доме. Между \(M\) парами домов есть дороги, и для каждой дороги известно, сколько времени потребуется для ее прохождения. Наконец, Милан знает, в каких \(K\) домах есть атомные укрытия и сколько людей помещается в каждое укрытие. Учитывая все это, у Милана возникает следующий вопрос: «Сколько времени нужно, чтобы эвакуировать всех жителей города?»

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

Конечно, эвакуация означает, что каждый житель попадает в какое-то атомное убежище. Можно предположить, что жители двигаются оптимально (по кратчайшему пути) и что несколько человек могут двигаться по одной дороге одновременно, возможно в разных направлениях. Также можно считать, что между любыми двумя домами есть хотя бы один путь, проходящий по дорогам.

Город Загреб решил построить новую парковку. Для этого было решено использовать прямоугольный участок земли, который можно представить в виде матрицы с \(N\) строками и \(M\) столбцами. Чтобы привлечь гостей и увеличить доходы, мэр решил разместить фонтаны на заранее определенных участках земли. Остальные же клетки будут преобразованы в парковочные места и дороги. Машины могут двигаться по парковке, перемещаясь в соседнее поле в одном из четырех направлений (север, юг, восток или запад). При этом парковочные места должны быть выбраны так, чтобы любая припаркованная машина могла выехать из парковки, то есть иметь возможность попасть в левую верхнюю клетку, не врезаясь в другие припаркованные машины.

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

Члены комиссии соревнования ICPC не смогли придумать задачи, поэтому они решили ранжировать команды лексикографически. Таким образом, победителем станет команда, название которой лексикографически самое маленькое. Героиня этой задачи, Этна, является лидером команды, личность которой мы будем скрывать. Название её команды начинается с буквы «Z», что ставит её в довольно плохое положение. После долгих разговоров с комитетом Этна смогла добиться более справедливого способа ранжирования команд. К сожалению, команды будут продолжать сортировать лексикографически, но определение лексикографического порядка изменится. А именно, комитет случайным образом выберет перестановку букв английского алфавита и определит лексикографический порядок, используя эту перестановку. Этна сразу же достала свой ноутбук и написала программу, которая находит перестановку букв для каждой команды, согласно которой эта команда выиграет соревнование. К сожалению, программа еще не закончена. Помогите Этне и напишите более эффективную программу с той же функциональностью.

Байтазар планирует заняться производством солнечных панелей. Он получил \(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\).