Перед тем, как задачи Moscow Programming Contest были отправлены в печать, жюри упорядочило задачи по возрастанию сложности, так что эта задача — самая простая, а задача K — самая сложная.

Алиса и Боб — участники одной из команд, прямо сейчас принимающей участие в том же самом контесте, что и вы. Их команда решила все задачи, кроме самой последней. Сейчас третий участник дописывает код последней задачи, Боб решил навести порядок на столе и сложил условия всех задач в стопку. Алиса перебирает стопку и грустно вздыхает каждый раз, когда название задачи начинается с буквы, которая идёт в алфавите раньше, чем буква, с которой начинается название предыдущей задачи.

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

Лена руководит разработкой тестирующей системы, в которой реализованы интерактивные задачи.

До заверщения очередной стадии проекта осталось написать модуль, определяющий итоговый вердикт системы для интерактивной задачи. Итоговый вердикт определяется из кода завершения задачи, вердикта интерактора и вердикта чекера по следующим правилам:

• Вердикт чекера и вердикт интерактора — это целые числа от 0 до 7 включительно.
• Код завершения задачи — это целое число от -128 до 127 включительно.
• Если интерактор выдал вердикт 0, итоговый вердикт равен 3 в случае, если программа завершилась с ненулевым кодом, и вердикту чекера в противном случае.
• Если интерактор выдал вердикт 1, итоговый вердикт равен вердикту чекера.
• Если интерактор выдал вердикт 4, итоговый вердикт равен 3 в случае, если программа завершилась с ненулевым кодом, и 4 в противном случае.
• Если интерактор выдал вердикт 6, итоговый вердикт равен 0.
• Если интерактор выдал вердикт 7, итоговый вердикт равен 1.
• В остальных случаях итоговый вердикт равен вердикту интерактора.

Ваша задача — реализовать этот модуль.

Межзвёздная автоматическая станция передала на Землю закодированное тестовое сообщение, состоящее из N сигналов — целых неотрицательных чисел, не превосходящих 255 (числа в сообщении могут повторяться). Но из-за ошибки в программе с принимающей стороны числа в сообщении были переставлены, а из-за зашумлённости канала связи некоторые сигналы были распознаны некорректно.

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

Число является существенно палиндромическим в системе счисления с основанием b ≥ 2, если запись этого числа в соответствующей системе без ведущих нулей состоит более, чем из одной цифры и является палиндромом.

Например, число 5 является существенно палиндромическим в системе счисления с основанием 2 (запись 101 является палиндромом), а числа 1 и 2 — не являются (запись 10 палиндромом не является, а запись числа 1 состоит из одной цифры); число 901684 является существенно палиндромическим в системе счисления с основанием 99 (так как 901684 = 99·99·91 + 99·98 + 91, то число состоит из цифр (91) в первом разряде, (98) во втором и (91) в третьем и тем самым запись является палиндромом).

По заданному числу n требуется найти максимальное целое число b ≥ 2 такое, что в системе счисления с основанием b число n является существенно палиндромическим.

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

Например, полный набор 3-полимино состоит из двух фигур,

а полный набор 4-полимино состоит из пяти фигур.

У Алёны есть полный набор n-полимино. Она считает некрасивыми все полимино, содержащие квадрат 2 × 2. По заданному n определите количество некрасивых полимино.

В некоторых комнатах лабиринта n × n расставлены указатели «север», «юг», «запад» и «восток». Остальные комнаты пусты. Робот стартует с некоторого поля и следует по указателям до тех пор, пока не выйдет из лабиринта или не попадёт на поле, в котором нет указателя. Стены в лабиринте отсуствуют, то есть робот может перейти на любое соседнее по стороне поле (или выйти из лабиринта, если он пошёл с края доски в соответствующую сторону).

Требуется выяснить, что произойдёт с роботом: зациклится ли он, покинет ли доску или придёт на какое-то свободное поле доски (в этом случае требуется указать, на какое именно).

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

Подсеть задаётся базовым IP-адресом и маской подсети.

• Базовый IP-адрес представляет собой 32-битовое целое число и задаётся как набор из 4 целых чисел от 0 до 255 включительно, записываемых через точку (например, "129.1.3.17"). Первое число соответствует старшему байту ip-адреса, последнее — самому младшему. То есть записи "129.1.3.17" соответствует двоичное число 10000001 00000001 00000011 00010001.
• Маска подсети M представляет собой целое число от 0 до 31 и обозначает количество старших бит IP-адреса, являющихся постоянными для всех адресов в данной подсети. То есть адрес принадлежит данной подсети тогда и только тогда, когда старшие M бит адреса и маски подсети совпадают.

  Маска подсети записывается через наклонную черту сразу после базового адреса. Например, "129.1.3.17/28". В данном случае маска равна 28, то есть подсеть включает в себя все IP-адреса с фиксированными 28 старшими битами 10000001 00000001 00000011 0001 (то есть адреса от "129.1.3.16" до "129.1.3.31" ).

• При этом существуют два специальных IP-адреса, которые не могут быть назначены: наибольший адрес (где в маске нулевые биты — в нём стоят единицы) соответствует широковещательному адресу, наименьший — адресу самой подсети (где в маске нулевые биты — в нём стоят нулевые биты). В случае с подсетью "129.1.3.17/28" это адреса "129.1.3.16" и "129.1.3.31", тем самым до подключения первого устройства всего в этой подсети доступны 14 адресов.

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

Напомним несколько классических определений. Пусть дан массив A из n целых чисел [a₁, a₂, ..., a_n]. Последовательность [b₁, b₂, ..., b_m] будет называть подмассивом данного массива, если существует такое l, 1 ≤ l ≤ n - m + 1, что a_l = b₁, a_l + 1 = b₂, ..., a_{l + m - 1} = b_m.

Разные массивы даже одинаковой длины могут иметь разное количество непустых подмассивов. Например, массив [1, 1, 1] имеет три различных подмассива ([1], [1, 1], [1, 1, 1]), в то время как массив [1, 2, 3] - шесть ([1], [1, 2], [1, 2, 3], [2], [2, 3], [3]).

Массивы можно сравнивать лексикографически. Массив C = [c₁, c₂, ..., c_k] лексикографически меньше массива D = [d₁, d₂, ..., d_l], если выполнено одно из двух условий:

1. Массив C короче массива D и является его префиксом, то есть k < l, и при этом c₁ = d₁, c₂ = d₂, ..., c_k = d_k;
2. В первой позиции, в которой они отличаются, у массива C стоит меньший элемент, то есть существует такое целое положительное p ≤ min(k, l), что c₁ = d₁, c₂ = d₂, ..., c_p - 1 = d_p - 1 и c_p < d_p.

А вот и условие задачи. Пусть дан массив A = [a₁, a₂, ..., a_n] и целое положительное число k. Упорядочим все подмассивы А в лексикографическом порядке. Какой подмассив идёт в полученном упорядоченном списке k-м?

Преподаватель Д. любит давать контрольные работы. Вот и завтра он очень хочет дать контрольную работу по геометрии.

Для формулировки очередной задачи Д. необходимо задать параллелограмм, ромб, квадрат и трапецию. У Д. есть список из n любимых точек; Д. хочет выбрать каждый из четырехугольников так, чтобы все его вершины были любимыми точками, а четырехугольники - невырожденными. Однако от обилия вариантов разбегались глаза, и было непонятно, с чего начинать выбор. Д., как принято в таких случаях, просит Вас написать программу, которая по списку любимых точек найдет четыре числа — количество способов выбрать параллелограмм, ромб, квадрат и трапецию.

Д. любезно напоминает, что выпуклый четырехугольник ABCD является:

• параллелограммом, если отрезок AB параллелен отрезку CD и AD параллелен BC;
• ромбом, если |AB| = |BC| = |CD| = |DA|;
• квадратом, если |AB| = |BC| и все четыре угла четырехугольника равны;
• трапецией, если AB параллелен CD и AD НЕ параллелен BC, либо AD параллелен BC и AB НЕ параллелен CD.

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

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

Напомним, что последовательность ребер (u₁, u₂), (u₂, u₃), ..., (u_k - 1, u_k), (u_k, u₁) является простым циклом, если вершины u₁, u₂, ..., u_k попарно различны. Простой цикл проходит через ребро e, если ребро e содержится в последовательности ребер цикла.

Петлёй в графе называется ребро (u, v), т.ч. u = v.

Рёбра (u₁, v₁) и (u₂, v₂) называются кратными, если u₁ = u₂ и v₁ = v₂.

Помогите Графине понять, является ли её Граф, являющийся ориентированным графом без петель и кратных ребер, колючим или нет.

Дан массив a₁, a₂, ..., a_n, каждое a_i равняется 0 или 1. Напишите программу, которая умеет выполнять две операции:

1. по заданным числам l и r (1 ≤ l ≤ r ≤ n) меняет каждое из чисел a_l, a_l + 1, ..., a_r на противоположное (0 на 1, 1 на 0);
2. для заданных чисел l и r, (1 ≤ l ≤ r ≤ n) рассматривает все подотрезки массива длиной от l до r, вычисляет для каждого из них сумму чисел на этом подотрезке, возвращает остаток от деления этой суммы по всем подходящим подотрезкам на 2. Формально, вычисляется величина: .