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

Чтобы облегчить себе задачу, Вася решил обратиться за помощью к прославленному игроку на тотализаторе осьминогу Паулю. Дело в том, что Вася знает, как осьминог делает свои безошибочные предсказания. Перед началом соревнований Пауль каким-то образом делит команды на три группы по силе: самые сильные команды, средние и самые слабые. Чтобы спрогнозировать результат игры, Пауль смотрит на силу команд, принимающих участие в матче. Если команды находятся в разных по силе группах, он выбирает команду, из более сильной с его точки зрения группы, иначе осьминог просто не знает, какая команда победит.

Для того, чтобы сделать точный прогноз на финальный матч, Вася очень хочет узнать, как же именно Пауль разбивает команды на группы по силе. Немного подумав, мальчик понял, что разбиение возможно восстановить по прогнозам осьминога. Для этого достаточно несколько раз задать ему вопрос вида: "Сильнее или слабее команда a чем команда b". К сожалению, Вася может задать осьминогу ограниченное число вопросов (не более 10⁶), иначе Пауль догадается, что мальчик хочет раскрыть его секрет.

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

На окружности отмечено \(2n\) различных точек, пронумерованных от 1 до \(2n\) против часовой стрелки. Петя нарисовал \(n\) хорд, \(i\)-я из которых соединяет точки с номерами \(a_i\) и \(b_i\). При этом каждая точка является концом ровно одной хорды.

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

Напомним, что палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, палиндромами являются строки “abba” и “madam”.

Для произвольной строки \(s\) введем операцию деления пополам, обозначаемую \(half(s)\). Значение \(half(s)\) определяется следующими правилами:

Если \(s\) не является палиндромом, то значение \(half(s)\) не определено;

Если \(s\) имеет длину 1, то значение \(half(s)\) также не определено;

Если \(s\) является палиндромом четной длины \(2m\), то \(half(s)\) — это строка, состоящая из первых \(m\) символов строки \(s\);

Если \(s\) является палиндромом нечетной длины \(2m+1\), большей \(1\), то \(half(s)\) — это строка, состоящая из первых \(m + 1\) символов строки \(s\).

Например, значения \(half(\mbox{inforamatics})\) и \(half(\mbox{i})\) не определены, \(half(\mbox{abba}) = \mbox{ab}\), \(half(\mbox{madam}) = \mbox{mad}\).

Палиндромностью строки \(s\) будем называть максимальное число раз, которое можно применить к строке \(s\) операцию деления пополам, чтобы результат был определен.

Например, палиндромность строк “informatics” и “i” равна 0, так как к ним нельзя применить операцию деления пополам даже один раз. Палиндромность строк “abba” и “madam” равна 1, а палиндромность строки “totottotot” равна 3, поскольку операция деления пополам применима к ней три раза: “totottotot” → “totot” → “tot” → “to”.

Рассмотрим все строки длины \(n\), состоящие из строчных латинских букв, палиндромность которых равна \(p\). Ваша задача — найти \(k\)-ю в алфавитном порядке среди этих строк.

В театре работает \(n\) актеров. Известно, что среди них \(a\) – высоких, \(b\) – голубоглазых и \(с\) – блондинов. Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин. Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать, какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.

Требуется написать программу, которая по заданным числам \(n\), \(a\), \(b\) и \(с\) определяет минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.

2
5 3 4 5

3

1
5 3 4 5

2