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

Пусть F(Q) – количество целых положительных чисел не больше Q, которые представимы в виде 2^x - 2^y при целых неотрицательных x, y. Упорядочим по возрастанию количества единичных бит в двоичном представлении все числа Q такие, что F(Q) = N. Если количество единичных бит в двух числах одинаково, большим считается то из них, значение которого больше. В качестве одноразового пароля выбирается K-е по порядку число.

Необходимо вычислить одноразовые пароли для T сессий аутентификации.

У Вани есть массив из N целых чисел a₁, a₂, ..., a_N. Он хочет вычислить сумму всех этих чисел. Но он также хочет, чтобы сумма чисел была неотрицательной, четной и при всем этом минимально возможной. Поэтому, он решил домножить одно из чисел на любое целое число перед тем как вычислять сумму.

Помогите Ване вычислить сумму, которую он хочет.

Однажды король Бандиатерры Барбато задумался о разделе своего королевства между своими сыновьями Филиппом и Фердинандом. Владения Барбато представляют собой N замков, которые для простоты обозначим точками с целочисленными координатами (X_i, Y_i). Король любит своих сыновей одинаково сильно, поэтому решил совершить раздел королевства в соответствии с кодексом справедливости Бандиатерры.

Для соблюдения законности раздел проводится по линии, параллельной оси ординат и проходящей через точку (X, 0). Замки, находящиеся к западу от границы (такие, что X_i ≤ X), отходят Филиппу, а те, что к востоку от границы (X < X_i) – Фердинанду. Город каждого из братьев представляет собой выпуклую оболочку множества замков, доставшихся по наследству. В соответствии с кодексом раздел тем справедливее, чем ближе модуль разности площадей городов к заданному числу S – сакральному числу Бандиатерры.

Барбато специально собрал совет старейшин Бандиатерры, чтобы определить заранее линию разграничения и записать ее в завещание.

Сегодня отовсюду трубят про выборы. Скандалы, интриги, расследования, разоблачения. В нашем городке Бездорожинске тоже настало время выбирать мэра. Но, чтобы избежать традиционных распрей, мы решили изменить концепцию: победителя определит не слово, а дело. И дело это очень важное — постройка дорог.

В Бездорожинске есть несколько микрорайонов, в которых построено N домов, соединенных M двунаправленными дорогами. Дорог, как водится, не хватает. Дороги между домами не дублируются, и нет дорог, петляющих и приводящих в тот же дом. В микрорайоне(который, к слову, может состоять из одного дома) между любой парой домов существует как минимум один путь по дорогам. А вот из микрорайона в микрорайон дорог нет, и бедным жителям приходится добираться по грязи.

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

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

После того, как вы узнаете текущую схему дорог в Бездорожинске, вам потребуется вывести одно из чисел: "1" или "2" — первым или вторым вы хотите начать предвыборную гонку, соответственно.

Теперь, если сейчас ваша очередь, то вам необходимо вывести два целых числа U V — номера домов, между которыми вы беретесь строить дорогу. Если сейчас ход вашего соперника, то вы получаете два целых числа U V — номера домов, которые соединил ваш оппонент.

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

После вывода не забывайте, пожалуйста, выводить символ новой строки и делать flush-операцию (сброс буфера). Например, fflush(stdout) в C++, System.out.flush() в Java, и flush(output) в Pascal.

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

Вова утверждает, что придумал новую сортировку. Его сортировка отличается тем, что она может отсортировать, по мнению Вовы, любую перестановку длины N при этом делая одни и те же сравнения для любой перестановки. Всего она делает M сравнений, где i-е сравнение происходит над числами, находящимися на позициях x_i и y_i соответсвенно.  Если на момент сравнения число находящееся на позиции x_i оказывалось больше, то она меняет их местами.

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

Жил-поживал на не совсем обычной шахматной доске не совсем обычный слон. Доска была не совсем обычной, так как была произвольного размера N × M. Слон был не совсем обычным, потому что стоял на угловой клетке. Стоял он, стоял, и заскучал. И решил отправиться в путешествие куда глаза глядят. А глаза у слонов, как известно, глядят по диагонали. Достигнув края доски, слон поворачивал на 90 градусов и продолжал движение. Остановился он только тогда, когда опять попал в какой-то (первый попавшийся) из углов.

Сколько всего уникальных полей слон обошел за свое путешествие по доске N × M ?

Туристическое агентство "42 лучших путешествия" выбрало для себя N городов, которые связаны между собой N - 1 прямыми авиарейсами так, что между двумя любыми городами существует авиамаршрут (возможно, непрямой). Для продвижения своих услуг агенство выбрало контекстную рекламу. Чтобы объявления были не слишком назойливыми, было решено показывать только уникальные туры. Под туром понимается посещение K (K ≤ N) городов, которые связаны K - 1 прямыми авиарейсами и между любыми двумя городами существует авиамаршрут. Туры считаются различными, если в одном из них существует такой город, которого нет в другом.

Придумав такую рекламную стратегию, директор агенства задумался о том, какие расходы понесет компания. За каждое объявление поставщик контекстной рекламы выставляет счет в один доллар США, а за каждый город, входящий в тур – один белорусский рубль. Теперь бухгалтерии необходимо выяснить, сколько агентство заплатит поставщику услуг, если известно, что все возможные уникальные туры были показаны пользователям ровно один раз.

Дана последовательность A_i, состоящая из N целых чисел. Найдите количество таких пар (L, R), для которых подотрезок {A_L, A_L + 1, ..., A_R} является перестановкой из R - L + 1 чисел. Перестановкой из K чисел называется любая последовательность чисел от 1 до K, в которой каждый элемент встречается ровно один раз.

Ваня построил последовательность f_i по следующему правилу:

1. f₀ = x, f₁ = y;
2. f_i = f_i - 1 + f_i - 2, i > 1.

К несчастью, Ваня потерял последовательность. Однако он помнит одно число N, принадлежавшее данной последовательности. Он также помнит, что все элементы последовательности являются целыми неотрицательными числами.

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

Компания "42 оттенка зеленого" состоит из N отделов. Для сплочения духа коллектива руководство компании попросило каждый из отделов придумать себе слоган, который представляет собой строку, состояющую из не менее чем K строчных символов латинского алфавита. Чтобы оценить работу всех отделов компании было решено общим слоганом выбрать лексикографически минимальную строку, которая содержала бы в себе хотя бы одну подстроку длины K от слоганов каждого из отделов. Поскольку бюджет на распечатку слогана ограничен, он не должен содержать лишних символов. Поэтому давайте для каждого лозунга отдела рассмотрим первое вхождение его любой подстроки длины K в общий лозунг и если существует символ, который не покрывается этими вхождениями, то такой символ лишний и его нужно удалить.

Помогите компании "42 оттенка зеленого" найти свой корпоративный слоган из заданных слоганов отделов.