Поликарп решил залезть в лабиринт. Лабиринт представляет собой N комнат, соединенных N - 1 коридорами. В начальный момент он находится в комнате 1, из которой он может дойти до любой другой. Находясь в очередной комнате, Поликарп пытается перейти из неё в комнату, в которой он еще не был. Если таких комнат нет, Поликарп переходит в комнату, из которой он пришел, или выходит из лабиринта, если он находится в комнате 1 и посетил все остальные комнаты. В каждой комнате записано определенное число. Поликарп определил, что в комнате i записано число a_i, повторенное b_i раз. Например, если a_i равно 123, а b_i — 3, число будет выглядеть как 123123123. Каждый раз, посещая очередную комнату, Поликарп записывает себе это число указанное число раз в блокнот. При этом считается, что в начальный момент Поликарп посещает комнату 1. Таким образом, у него получается еще одно число c, составленное из всех выписанных чисел. Поликарпа интересует все подпоследовательности подряд идущих одинаковых цифр. Среди таких подпоследовательностей он выбирает те, у которых длина наибольшая, а среди них он выбирает ту, которая составлена из наименьшей цифры. Ему нужно определить, из какой минимальной цифры и максимальной длины можно составить такую подпоследовательность.

У Поликарпа есть массив из N целых чисел a₁, ..., a_N. Над этим массивом Поликарп проводит опыты, а именно, применяет к нему некоторый набор операций. Всего операций M. Есть три типа операций. Первый тип задается строкой вида: 1 L R — это означает уменьшить числа в массиве на позициях L, ..., R на 1. Второй тип выглядит так: 2 L R — это означает увеличить числа в массиве на позициях L, ..., R на 1. Третий и последний тип выглядит как 3 L R a₀ a₁ a₂ a₃ a₄. Он означает: вычислите , где f(x_i) = a₀·x_i⁴ + a₁·x_i³ + a₂·x_i² + a₃·x_i¹ + a₄ и x_i — число в массиве на позиции i. Вам необходимо последовательно выполнить заданный набор операций.

Гарантируется, что в любой момент времени числа в массиве не превышают по модулю 200. Все значения сумм не превышают по модулю 10¹⁸.

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

Поликарп решил помочь с организацией олимпиады и сделать для каждой команды логины. У него есть таблица из N + 1 строк и M столбцов в формате csv. Это означает, что таблица представляет собой текст из N + 1 строк. Каждая строка i имеет вид "a_i, 1;a_i, 2;... ;a_i, m" (без кавычек), где a_i, j — содержимое ячейки на пересечении строки i и столбца j. Содержимое каждой ячейки представляет собой строку длиной от 1 до 30 символов. Ячейка может содержать только строчные и прописные латинские символы и цифры. В первой строке находятся названия столбцов. Среди них обязательно есть "Team", "City", "Email", "Organization", "Participant1", "Participant2" и "Participant3" — название команды, город, адрес электронной почты, название организации и ФИО участников соответственно. Столбцы могут идти в любом порядке.

Поликарпу необходимо сделать еще одну таблицу в таком же формате с полями "Team", "Login", "Email", "Participants" — название команды, логин, электронная почта и участники соответственно. Логин выглядит как "team<XXX> (<Organization>, <City>)", где <XXX> - трехзначный номер команды в исходной таблице, Organization и City — названия организации и города соответственно. Участники заполняются так : "<Participant1>,<Participant2>,<Participant3>" — ФИО участников через запятую.

У Поликарпа есть плоскость с N кругами на ней и бесконечно длинная нитка. Каждый круг i задается координатами центра x_i и y_i и радиусом r_i. Поликарп использует нитку, чтобы обтянуть все эти круги так, чтобы все круги были внутри фигуры, образованной ниткой. При этом нитку разрезать нельзя.

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

У Поликарпа появилось новое увлечение — спутникостроение. Подглядел он идею у компании Provectus. Ну, так вот, он узнал, что вместо одного дорогостоящего многотонного спутника, который еще надо выводить на орбиту ракетой, достаточно отправить N маленьких спутников массой несколько килограмм каждый, которые выводятся на орбиту с помощью специальных самолетов, а это в разы дешевле. Но тут у него возникла задача передачи данных между спутниками. Между любыми двумя различными спутниками можно настроить один двухсторонний канал связи. Но так как это требует установки на спутник дополнительного оборудования, то суммарное число всех каналов связи не более 4·N.

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

У Поликарпа есть строка S, стоящая из N строчных латинских символов. Поликарпа интересует, являются ли определенные подстроки строки S палиндромами. Палиндромом называется строка, которая одинаково читается справа налево и слева направо. Но этого Поликарпу мало: он еще может менять символы в строке. Поликарпу интересно, можно ли быстро определять, является ли палиндромом заданная подстрока строки S, если в S можно заменять символы. Всего Поликарп последовательно проводит K операций.

У Поликарпа есть набор из N слотов, в каждом слоте расположено по одному украшению. У каждого украшения есть уникальный номер — целое число из интервала [1... N]. Также у Поликарпа есть набор из M базовых и K составных операций. Базовые операции называются цепочками. Каждая цепочка с номером i задается числом bl_i и числами b_i, 1, ..., b_i, bli. Все числа b_i, j целые, различны для одной цепочки и лежат в интервале [1... N]. Это означает следующее: украшение из позиции b_i, j переходит в позицию b_{i, j + 1} для 1 ≤ j < bl_i. Украшение из позиции b_i, bli переходит в позицию b_i, 1. Составная операция с номером i описывается так: указывается число cl_i и cl_i пар чисел co_i, j и cc_i, j. Каждая пара означает применить цепочку co_i, j cc_i, j раз.

Поликарп проводит опыты над этим набором. Перед началом каждого опыта в i-й слот помещается i-е украшение. Опыт i описывается числом el_i и el_i парами чисел eo_i, j и ec_i, j. Каждая пара означает применить составную операцию eo_i, j ec_i, j раз. Поликарпу интересно узнать, что окажется в каждом слоте после выполнения очередного опыта.

В очередной раз Поликарп решил провести опыт. В этот раз у него есть набор треугольных теплообменников, расположенных на поле. У каждого теплообменника i есть две части — вход и выход, а также входной и выходной коэффициенты kin_i и kout_i соответственно. Если два теплообменника касаются или пересекают друг друга, то их входы сплавливаются в один с коэффициентом k, который считается по формуле , где k₁ и k₂ — входный коэффициенты исходных входов теплообменников. Из каждой точки поля выходит некоторое количество тепла в секунду. Это количество умножается на входной коэффициент сплавленных входов и на произведение выходных коэффициентов теплообменников, которую содержат данную точку. Известно, что из квадрата с длиной 1 на поле выходит 1 единица тепла. Поликарпу интересно узнать, сколько тепла выделяют теплообменники.

У Поликарпа есть немного свободного времени, набор N десятичных цифр c₁, ... , c_N и положительное число A. Он хочет найти такое положительное число B, такое, что B кратно A и B состоит из цифр набора {c_i}, 1 ≤ i ≤ N. Каждую цифру из набора можно использовать произвольное число раз. Необязательно использовать их все.

Поликарп по-прежнему продолжает опыты с освещением. В этот раз он освещает цилиндр множеством прозрачных лампочек. Центр нижнего основания находится в точке (x_c, y_c, 0), его высота равна h, радиус равен r. Нижнее основание лежит в плоскости xOy, верхнее параллельно ему и с центром в точке (x_c, y_c, h). Также Поликарп приготовил N лампочек, i-я лампочка находится в точке (x_i, y_i, z_i). Размером лампочек можно пренебречь. Лампочки очень мощные, поэтому они освещают все точки пространства, на пути к которым нет препятствий. Цилиндр сплошной и не пропускает свет. Поликарпу интересно узнать площадь освещенной части поверхности цилиндра.

У Поликарпа есть набор чисел 1, ..., N, а также параметры M и K. Поликарпа интересует количество перестановок {a_i} из чисел 1, ..., N, таких, что в них ровно M инверсий и K чисел на своем месте. Инверсией называется пара чисел i, j, таких, что a_i > a_j и i < j. Число i находится на своем месте, если a_i = i.