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

На одной из стен зала видеонаблюдения расположена панель, представляющая собой прямо- угольник, состоящий из \(n\) горизонтальных рядов по \(m\) мониторов в каждом. На каждый монитор выводится изображение с камеры, находящейся в одном из зданий. Зал видеонаблюдения оборудован инновационным пультом управления с четырьмя кнопками: «влево», «вправо», «вверх» и «вниз».

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

Аналогичным образом действуют кнопки «вправо», «вверх» и «вниз». Кнопка «вправо» перемещает изображение с каждого монитора на монитор, находящийся справа от него. Изображения из самого правого монитора в каждом ряду перемещаются на самый левый монитор этого ряда. Кнопка «вверх» перемещает изображение с каждого из мониторов на монитор, находящийся над ним. Изображения из самого верхнего ряда перемещаются на мониторы самого нижнего ряда. Кнопка «вниз» перемещает изображение с каждого из мониторов на монитор, находящийся под ним. Изображения из самого нижнего ряда перемещаются на мониторы самого верхнего ряда.

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

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

Это интерактивная задача.

При проведении раскопок на территории Республики Татарстан были обнаружены останки неизвестного древнего животного, обитавшего в окрестностях современной Казани миллионы лет назад. Как и у всех живых организмов, молекула его ДНК представляет собой последовательность из n нуклеотидов, однако число встречающихся в ней различных нуклеотидов может отличаться от современных организмов.

Для изучения находки был создан специальный прибор, который может просканировать последовательный участок нуклеотидов в ДНК и вычислить, сколько различных видов нуклеотидов содержится на нём. К сожалению, молекула ДНК может выдержать не более \(q\) операций сканирования, после чего разрушается.

Исследователи хотят с помощью этого прибора найти \(k\) — количество различных нуклеотидов в ДНК, и определить позиции, в которых в ДНК находятся одинаковые нуклеотиды. Ученые хотят закодировать последовательность нуклеотидов в молекуле последовательностью целых положительных чисел \(a_1, a_2, \dots, a_n (1 \le a_i \le k)\), таких что одинаковые числа кодируют одинаковые нуклеотиды, а различные числа — различные нуклеотиды.

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

В корпорации работают \(n\) сотрудников, один из которых является директором. У каждого сотрудника, кроме директора, имеется ровно один непосредственный руководитель.

Каждый сотрудник выполняет свою строго определённую работу. Если сотруднику a требуется выполнить работу, которой занимается сотрудник \(b\), то он должен отправить сотруднику \(b\) заявку. Согласно корпоративной политике напрямую заявки могут передаваться только либо от сотрудника его непосредственному руководителю, либо наоборот — от руководителя к непосредственному подчинённому. Заявка передается от сотрудника к сотруднику до тех пор, пока не достигнет сотрудника \(b\).

Чтобы разгрузить сотрудников, корпорация наняла \(k\) курьеров. Курьер с номером \(i\) закреплён за парой сотрудников \(a_i\) и \(b_i\) и занимается доставкой заявок между ними. Если одному сотруднику из этой пары требуется передать заявку другому, то он отдает заявку курьеру, который последовательно передает заявку между сотрудниками в соответствии с корпоративной политикой, пока заявка не пройдет всех необходимых промежуточных сотрудников и окажется доставленной адресату. В процессе доставки одной заявки курьер не посещает одного и того же сотрудника более одного раза.

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

Требуется написать программу, которая определит двух курьеров с наибольшей степенью дублирования.

Современный робот-программист должен владеть слепым \(10_2\)-пальцевым методом набора бинарных строк, состоящих из символов «0» и «1». В инновационном тренажёре, созданном специально для уже освоивших \(10_2\)-пальцевый набор роботов, предлагается следующее упражнение. В верхней части экрана выводится строка, состоящая из нулей и единиц. Ниже выводятся пары \((c_i, w_i)\), каждая из которых состоит из бинарного слова \(w_i\) и его стоимости \(c_i\) — количества штрафных баллов, начисляемых за каждое использование слова \(w_i\) при наборе строки.

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

Префиксом слова называется последовательность подряд идущих символов этого слова, начинающаяся с первого символа слова, а суффиксом — последовательность подряд идущих символов этого слова, заканчивающаяся последним символом слова. Слово целиком является как своим префиксом, так и своим суффиксом.

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