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

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

Король Байтазар считает, что Байтотия — земля, полная красивых достопримечательностей — должна привлечь множество туристов, которые должны потратить много денег, которые в конечном счете должны найти свой путь в королевскую казну. Но реальность далека от мечты. Поэтому король поручил своему советнику изучить этот вопрос. Советник выяснило, что иностранцы держаться подальше от Байтотии из-за ее плохой дорожной сети. В Байтотии \(n\) городов соединенных \(m\) двусторонними дорогами. Не гарантируется, что от каждого города можно добраться от любого другого города. Советник отметил, что нынешний дорожная сеть не позволяет делать длительные путешествия. А именно, где бы вы не начали поездку, невозможно посетить более 10 городов не прохождения через какой-то город два раза. Из-за ограниченных средств в казне, новые дороги построить нельзя. Вместо этого, Байтазар решил создать сеть туристическо-информационных пунктов (ТИП), которые будут рекламировать короткие путешествия. Для каждого города должен быть ТИП либо в нем, либо в одном из городов, непосредственно связанных с ним дорогой. Кроме того, известна стоимость строительства ТИПа в каждом из городов. Помогите королю найти самый дешевый спосою построить ТИПы, так, чтобы это условие удовлетворялось.

Центр Гдынии расположен на острове посередине реки Кацза. Каждое утро тысячи машин едут из жилых районов на западном берегу в индустриальные на восточном.

Остров можно представить в виде прямоугольника \(A\times B\) со сторонами, параллельными осям координат, углами \((0, 0)\) и \((A, B)\).

На острове есть \(n\) перекрёстков, пронумерованных натуральными числами от \(1\) до \(n\). Перекрёсток номер \(i\) имеет координаты \((x_i, y_i)\). Если координаты какого-то перекрёстка имеют вид \((0, y)\), то он находится на западном берегу, если \((A, y)\) - на восточном. Перекрёстки соединены дорогами, каждая - отрезок на плоскости, они не пересекаются (кроме концов). Дороги бывают односторонними и двусторонними. Нет никаких мостов и туннелей! Некоторые дороги могут идти по краям прямоугольника.

Поскольку плотность траффика растёт, мэр города нанял Вас (кого же ещё) проверить, достаточно ли текущей сети дорог. Он попросил написать программу, которая по карте города определит для каждого перекрёстка на западном берегу, сколько из него достижимых на восточном.

Поздравляем! Вас наняли управляющим одного крупного завода по производству чего-то очень важного. На вашем заводе есть \(n\) рабочих и \(n\) станков. Каждый рабочий умеет работать на каких-то станках, а на каких-то не умеет. К счастью, вы можете отправить какого-то рабочего на курсы повышения квалификации, чтобы он научился работать на каком-то станке, заплатив за это 1 тугрик. Нет никаких ограничений по тому, кого и сколько раз отправлять на курсы. У ваших работников также очень хорошая память, поэтому если они умели или научились работать на каком-то станке, то уже никогда не забудут, как это делать.

Но не все так радужно. Из-за кризиса сократили всех других менеджеров, поэтому рабочие сами определяют, за каким станком им работать в определенный день. Рабочие могут прийти на работу в случайном порядке. Когда рабочий пришел на работу он может выбрать любой еще не занятый станок, на котором умеет работать, и сядет за него. Если же такого не нашлось, то он расстроится и уйдет домой, а ваш завод понесет убытки. Так, если у вас было два рабочих, первый из которых умел работать на 1 и 2 станке, а второй только на первом, то если первый пришел на работу раньше и занял первый станок, то ваш завод понесет убытки.

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