Алгоритмы

Для идентификации ресурсов в сети Internet используются URL (Uniform Resource Locator). URL состоит из нескольких элементов: протокол, хост, порт, путь, файл и секция. Некоторые элементы URL могут быть опущены. Рассмотрим упрощенный формат URL:

[протокол://]хост[:порт][путь/[файл[#секция]]]
Заключенные в квадратные скобки элементы могут быть опущены, т.е. например, можно не указать протокол или секцию. Но, например, если указан файл, то обязательно должен быть указан путь. Регистр букв в элементах URL не важен.

Рассмотрим кратко все элементы URL:

*Протокол - это способ доступа к файлу, URL с разными протоколами и одинаковыми остальными элементами могут указывать на различные ресурсы.
*Хост и порт - это имя некоторого сервера в сети и способ доступа к нему (порт - натуральное число, не превосходящее 65535).
*Путь представляет собой путь к файлу, содержащему запрашиваемый ресурс, от некоторого каталога на сервере, который называется корневым. При этом для разделения имен каталогов используется символ "/". Путь, если он не пуст, всегда начинается с символа "/". Специальное обозначение '.' соответствует самому каталогу, '..' - родительскому каталогу.
*Файл - это файл, содержащий запрашиваемый ресурс.
Наконец, файл может быть разбит на секции каким либо способом и можно указать, к какой именно секции вы хотите обратиться.

Различные символы в URL могут быть заменены своими шестнадцатеричными ASCII кодами с помощью символа %, например a = %41, Z = %5A. В коде всегда используется ровно две шестнадцатеричные цифры.

Некоторые символы могут встречаться в элементах URL только как шестнадцатеричные коды - все символы, кроме букв латинского алфавита, цифр и символов "." и "-", а некоторые не могут встречаться вообще: "\", "#", "*", "@", "%", "?", ":", ",", а также символы с ASCII-кодом меньше %20. Символ "/" может встречаться в элементах URL только в пути для разделения входящих в него каталогов. Имя файла не может состоять только из точек.

Рассмотрим примеры URL:

http://neerc.ifmo.ru/school
ftp://somewhere.net:1234/pub/files/coolgame.zip
nobody.nowhere.net/some%20dir/some%20file#some%20info


Ваша цель в этой задаче - помочь разработчикам web-сервера. Для web-сервера отсутствующие части URL имеют следующие значения по умолчанию:

Протокол	http
Порт	80
Путь	пустая строка
Файл	index.html
Секция	пустая строка

Различные как строки URL могут указывать на один и тот же ресурс, например следующие три URL:

neerc.ifmo.ru
http://neerc.ifmo.ru:80/index.html#
Http://NEERC.IFMO.Ru/Dir/../././

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

Входные данные
Входные данные состоят из двух строк, каждая из них содержит URL. Оба URL удовлетворяют формату, приведенному в условии этой задачи. Длина каждого URL не превосходит 200 символов. Гарантируется, что ни один из промежуточных каталогов на пути к ресурсу не лежит выше корневого каталога (т.е. не может встретиться, например, URL http://somewhere.com/../dir/index.html) а также, что имена всех каталогов состоят по крайней мере из одного символа (два символа "/" не могут идти подряд в любом месте, кроме как непосредственно после двоеточия после имени протокола).

Выходные данные
Выведите YES, если оба URL, приведенные во входных данных, указывают на один и тот же ресурс, и NO в противном случае.

Государство Флатландия представляет собой прямоугольник размером M × N, состоящий из единичных квадратиков. Флатландия разделена на K провинций (2 <= K <= 100). Каждая провинция представляет собой связное множество квадратиков, т.е. из каждой точки провинции можно дойти до любой другой ее точки, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). Во Флатландии нет точки, которая граничила бы более чем с тремя провинциями (т.е. четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным провинциям).

Каждая провинция имеет свой символ. Столица Флатландии находится в провинции, которой принадлежит символ A (заглавная латинская буква A). Провинция называется пограничной, если она содержит граничные квадратики. Провинция, в которой находится столица Флатландии, не является пограничной.

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

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

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

Входные данные
В первой строке вводятся числа M и N (3 <= M, N <= 200). Следующие M строк содержат N символов каждая и задают карту Флатландии. Символ, находящийся в i + 1-й строке входных данных на j-м месте, представляет собой символ провинции, которой принадлежит квадратик (i, j). Все символы имеют ASCII-код больше 32 (пробела).

Выходные данные
Выведите единственное число - количество провинций, которые требуется захватить. Если установить блокаду невозможно, выведите "-1".

У Пети есть набор из N кирпичиков. Каждый кирпичик полностью окрашен в один из K цветов, i-й кирпичик имеет размер 1×1×Li. Петя знает, что он может построить из всех кирпичиков прямоугольную стену толщиной 1 и высотой K, причем первый горизонтальный слой кирпичиков в стене будет первого цвета, второй - второго и т. д. Теперь Петя хочет узнать, может ли он из своего набора построить две прямоугольные стены, обладающие тем же свойством. Помогите ему выяснить это.

Входные данные
В первой строке входных данных задаются числа N и K (1 <= N <= 5000, 1 <= K <= 100). Следующие N строк содержат описание Петиных кирпичиков: сначала длина L_i, затем номер цвета C_i (1 <= L_i <= 100, 1 <= C_i <= K). Известно, что у Пети не более 50 кирпичиков каждого цвета.

Выходные данные
Выведите в первой строке YES, если Петя сможет построить из всех своих кирпичиков две прямоугольные стены высоты K, j-й слой кирпичиков в каждой из которых будет j-го цвета, и NO в противном случае. В случае положительного ответа, выведите во второй строке в произвольном порядке номера кирпичиков, из которых следует построить первую стену (кирпичики нумеруются в том порядке, в котором они заданы во входных данных, начиная с 1). Если решений несколько, можно выдать любое из них.

В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат - ловушку для космического мусора. Для того, чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (N), на юг (S), на запад (W), на восток (E), вверх (U) и вниз (D). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {N, S, W, E, U, D}.

Команда ловушки есть пара из символа направления и параметра - целого положительного числа M. При исполнении такой команды ловушка в соответствии со своей программой выполняет следующее. Если параметр больше 1, то она перемещается на один метр в направлении, которое указано в команде, а затем последовательно выполняет команды, заданные правилом для данного направления, с параметром меньше на 1. Если же параметр равен 1, то просто перемещается на один метр в указанном направлении.

Пусть, например, заданы следующие правила:

Направление	Правило
N	N
S	NUSDDUSE
W	UEWWD
E
U	U
D	WED

Тогда при выполнении команды S(3) мусорщик выполнит следующие действия:
1) переместится на 1 метр в направлении S
2) выполнит последовательно команды N(2), U(2), S(2), D(2), D(2), U(2), S(2), E(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:

SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEEПо заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.

Входные данные
Первые шесть строк входных данных задают правила для команд с направлением N, S, W, E, U и D соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {N, S, W, E, U, D}, затем пробел и параметр команды - целое положительное число, не превышающее 100.

Выходные данные
Выведите единственное число - количество перемещений, которое совершит ловушка. Гарантируется, что ответ не превышает 10⁹.

Ваня и Петя играют в следующую игру. Ваня пишет на бумаге какую-либо перестановку чисел от 1 до N (то есть выписывает все числа от 1 до N в некотором порядке) и расставляет на столе в ряд N предметов. После этого Петя переставляет предметы в соответствии с Ваниной перестановкой. А именно, Петя выполняет следующие действия: если i-ое число в Ваниной перестановке равно a_i, то Петя ставит предмет, который стоит на i-ом месте, на место с номером a_i.

Обозначим предметы числами от 1 до N. Тогда начальное расположение предметов можно обозначить последовательностью чисел (1, 2, ..., N). К примеру, если N = 5, то начальное расположение предметов есть (1, 2, 3, 4, 5). Пусть Ваня написал перестановку <2, 5, 4, 3, 1>. Это значит, что после перемещения предметов они окажутся расставлены в следующем порядке: (5, 1, 4, 3, 2).

Однако, переставив предметы, Петя не останавливается на достигнутом и вновь переставляет их в соответствии с Ваниной перестановкой. Снова, если i-ое число в Ваниной перестановке равно a_i, то Петя ставит предмет, который стоит на i-ом месте на место с номером a_i. Так, если в приведенном выше примере повторно применить перестановку, предметы окажутся расположены в следующем порядке: (2, 5, 3, 4, 1).

Таким образом, Петя переставляет предметы в соответствии с Ваниной перестановкой, пока их расположение не окажется таким же, как исходное. В нашем примере Пете потребуется сделать еще 4 действия, порядок предметов после каждого из них будет следующим: (1, 2, 4, 3, 5), (5, 1, 3, 4, 2), (2, 5, 4, 3, 1), (1, 2, 3, 4, 5). Всего Пете потребовалось применить перестановку 6 раз.

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

Входные данные
Вводится единственное целое число N - количество предметов (1 <= N <= 100).

Выходные данные
Выведите перестановку чисел от 1 до N такую, что количество действий, которое придется сделать Пете, максимально. Если таких перестановок несколько, можно вывести любую.

В некотором царстве, в некотором государстве было N  городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|.

Император решил построить N+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.

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

Входные данные
В первой строке вводится число N - количество городов (1 <= N <= 100). Следующие N строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.

Выходные данные
Выведите два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.

Издательская система LATEX предназначена для верстки сложных научно-технических текстов с большим количеством формул. Исходный файл для системы LATEX пишется на языке TEX и представляет собой текст документа, в который включены специальные символы и команды. Специальные символы и команды описывают размещение текста, в частности в математических формулах. Команда представляет собой последовательность латинских букв (регистр важен), перед которой стоит символ "\". Так, команда \frac предназначена для описания дроби, в которой числитель расположен над знаменателем. Рассмотрим простейшую структуру команды \frac.

Команда \frac имеет два параметра — числитель и знаменатель. Перед самой командой не обязательно ставить пробел. Следом за ключевым словом frac записываются числитель и знаменатель. Если числитель и знаменатель имеют длину более одного символа, они заключаются в фигурные скобки. Если числитель или знаменатель записываются одной буквой или цифрой, их можно не брать в фигурные скобки. Если числитель записывается одним символом, то он отделяется от \frac хотя бы одним пробелом. Если знаменатель записывается одним символом, то он не отделяется пробелом от числителя. Произвольное ненулевое количество пробелов считается синтаксически эквивалентным одному пробелу. Нельзя разделять пробелами на части ключевое слово \frac.

Дадим также формальное определение выражения для нашей задачи:

<выражение> ::= <элемент> | <элемент><выражение>
<элемент> ::= <дробь> | "{" <выражение> "}" | <другой математический элемент>
<дробь> ::= "\frac" <тело дроби>
<тело дроби> ::= <числитель><знаменатель>
<числитель> ::= <пробелы><непробельный символ> | [<пробелы>] "{" <выражение> "}"
<знаменатель> ::= <непробельный символ> | [<пробелы>] "{" <выражение> "}"
<другой математический элемент> ::= произвольная последовательность печатных символов, не содержащая фигурных скобок и подстроки "\frac"
<пробелы> ::= " " | " " <пробелы>
<непробельный символ> ::= произвольный печатный символ, за исключением " ", "", "{" и "}"

Здесь вертикальная черта | означает "или", заключенная в квадратные скобки часть может отсутствовать, а символы, записанные в кавычках обозначают самих себя. Печатный символ - любой символ с ASCII кодом от 32 (пробел) до 127. Например, выражение


записывается на языке TEX как

\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}

Чтобы в печатаемом документе вывести формулу, необходимо вычислить ее высоту для используемого при печати шрифта. Шрифт определяет размеры S
 - высоту отдельного символа и D
 - высоту горизонтальной дробной черты. Значения S
 и D
 задаются целыми числами. Ваша задача - для заданного выражения на языке TEX вычислить высоту формулы.

Отметим, что если две дроби принадлежат одному выражению, то их дробные черты записываются на одном уровне, а если нет (например, относятся к числителям или знаменателям различных дробей), это свойство может и не выполняться. Чтобы проиллюстрировать применение этого правила, приведем два примера:

\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}


\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}

Входные данные
В первой строке вводятся целые положительные числа S и D (1 <= S, D <= 10000). Следующая строка содержит описание формулы на TEX-е, длина строки не более 200 символов. Гарантируется, что формула синтаксически корректна, то есть фигурные скобки образуют правильную скобочную последовательность и строка содержит только печатные символы. Все символы "", встречающиеся в строке относятся к некоторой командной последовательности (не обязательно \frac), можете считать, что все прочие командные последовательности задают символы, высота которых равна S. Числитель и знаменатель каждой дроби содержат хотя бы по одному символу, вся формула содержит хотя бы один символ.

Выходные данные
Выведите единственное число - высоту формулы.

Рассмотрим выпуклый многоугольник, вершины которого лежат в точках плоскости с целыми координатами. Требуется разбить его на треугольники с вершинами в точках с целыми координатами, каждый из которых имел бы площадь 1/2, либо выяснить, что это сделать невозможно.

Входные данные
В первой строке вводится число N - количество вершин многоугольника (1 <= N <= 10). Следующие N строк содержат координаты вершин многоугольника в порядке обхода их по часовой стрелке. Все координаты - целые неотрицательные числа, не превышающие 10. Никакие три последовательные вершины многоугольника не лежат на одной прямой.

Выходные данные
Если выполнить разбиение указанным образом невозможно, выведите единственное число - 0. В противном случае выведите несколько строк, содержащих по 6 чисел каждая. Количество строк должно быть равно количеству треугольников в найденном разбиении. Числа в каждой строке должны представлять собой координаты вершин соответствующего треугольника - x₁, y₁, x₂, y₂, x₃, y₃. Площадь каждого треугольника должна быть 1/2. Порядок перечисления треугольников и вершин в каждом из треугольников может быть произвольным. Если допустимых разбиений несколько, выведите любое.

В одном государстве имеется N городов. Некоторые города соединены дорогами, причем для любых двух городов A и B выполняется следующее свойство: существует ровно один способ попасть из города A в город B если можно перемещаться только по дорогам и не разрешается проезжать по одной и той же дороге более одного раза.

Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов A, B и C минимальное количество дорог, которое необходимо использовать, чтобы доехать от A до B, затем от B до C и затем от C до A (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).

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

Например, для пяти городов, соединенных дорогами так, как это показано на рисунке 1, три наиболее удаленных друг от друга города - это города 1, 2 и 5 (взаимная удаленность равна 2 + 3 + 3 = 8), а для городов на рисунке 2 - это любые три города, выбранные из множества {1, 2, 4, 5} (удаленность 2 + 2 + 2 = 6).

Входные данные
В первой строке вводится число N - количество городов (3 <= N <= 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит K_i - количество городов, с которыми он соединен дорогами (1 <= K_i < N), а затем K_i чисел - номера городов, с которыми он соединен. Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.

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

Играют двое. Задаётся какая-то дата 2020 года. Каждый игрок на своём ходе называет более позднюю дату, увеличивая на 1 или 2 либо день в месяце, либо месяц, но не то и другое сразу. При этом сочетание дня и месяца должно оставаться датой. Игрок, назвавший 31 декабря, проигрывает. Оба играют наилучшим образом. Исходя из заданной даты вывести, кто выиграет.

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

Выходные данные
Вывести 1, если выигрывает первый (начинающий) игрок, или 2 - в противном случае.

Витя и Денис играли в игру «Быки и коровы». Витя загадал четырёхзначное число с неповторяющимися цифрами, а Денис пытался это число угадать. Для этого он предлагал свои четырёхзначные числа (тоже с неповторяющимися цифрами), а Витя про каждое из них сообщал, сколько в нём «быков» (т. е. цифр, которые не только присутствуют и в Витином числе, и в числе Дениса, но даже стоят на одних и тех же местах) и «коров» (цифр, которые присутствуют в обоих числах, но стоят на разных местах). У них осталась запись партии (последовательность тестовых чисел и ответов на них), но задуманное число утратилось. Восстановите задуманное число.

Входные данные
Вводится сначала число N—количество четырёхзначных чисел,названных Денисом в одной партии (N < 100).Затем вводятся
N строк, по три числа в каждой. Первое — четырёхзначное число, названное Денисом (оно не начинается с нуля), второе — количество «быков», третье — количество «коров».

Выходные данные
Требуется вывести одно четырёхзначное число, задуманное Витей. Это число не начинается с 0.

Гарантируется, что ответ в задаче существует и является единственным

На странице сайта размещена карусель с фотографиями. Фотографии в карусели пронумерованы от 1 до n. Карусель содержит кнопки вперед и назад. При нажатии кнопки вперед, в карусель загружается следующая фотография (фотография с номером на 1 больше). Если в каруселе отображается последняя фотография (с номером n), то при нажатии кнопки вперед загружается первая фотография (фотография с номером 1).
Всего карусель содержит n фотографий. Посетитель сайта сейчас просматривает фотографию с номером m. Фотография под каким номером загрузится в карусель, если посетитель нажмет один раз кнопку вперед?

Формат входных данных
Программа получает на вход две строки. В первой строке записано натуральное число n (n < 10⁹). Во второй - натуральное число m (1≤ m ≤ n). 

Формат выходных данных
Выведите одно число - номер следующей фотографии.

От организаторов олимпиады поступил заказ на покупку N пачек бумаги "Снегурочка". Магазин упаковывает бумагу по M пачек бумаги в одну коробку. Последняя коробка может быть неполной. Определите, какое количество пачек бумаги будет в последней коробке. 

Формат входных данных
В первой строке входных данных записано натуральное число N - количество пачек, которые были заказаны. Во второй строке - натуральное число M - максимальное число пачек, которое помещается в одну коробку.

Формат выходных данных
Выведите одно число - ответ на задачу

Назовем таблицу из N  x M  чисел отсортированной, если любое число в таблице не меньше каждого из чисел, стоящих одновременно выше и левее данного числа (см. пример). Дана таблица чисел. Требуется переставить числа так, чтобы таблица оказалась отсортированной. Если способов несколько, нужно привести любой из них.

Входные данные
Вводятся сначала два числа N  и M  (натуральные, не превосходящие 30), а затем N  строк по M  разделенных пробелами чисел в каждой. Числа целые и не превышают по модулю 10000.

Выходные данные
Вывести N  строк по M разделенных пробелами чисел в каждой строке.

Мальчик Антон решает вступительную работу в летний математический лагерь. В ней N заданий, которые можно выполнять в произвольном порядке. Разные задачи требуют разного времени для решения. При этом известно, что если задание с номером i выполнять j-м по счету, Антону потребуется T_i*j
 времени: чем больше думаешь, тем больше устаешь. Например, если начать с первой задачи, а затем выполнить вторую, то потребуется T₁*1 + T₂*2 времени, а если выполнить сначала вторую задачу, а затем первую – то T₂*1 + T₁*2. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени.

Входные данные
В первой строке вводится число N, во второй строке —N чисел через пробел T₁, T₁, …, T_N, разделенные пробелами. Все числа целые и удовлетворяют следующим ограничениям: 0 < N ≤ 10, 0 < T_i ≤ 100.

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

Примеры

№	Входные данные	Выходные данные
1	1 23	23 1
2	2 52 37	126 1 2

Электронная таблица представляет собой прямоугольную таблицу, левая и верхняя граница которой зафиксированы, а правая и нижняя отсутствуют, таким образом, таблица бесконечна вправо и вниз. В каждой ячейке таблицы может быть записано какое-либо значение. Значение ячейки – это произвольная последовательность символов с кодами от 32 до 126.

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

Значения соседних ячеек при записи в файл разделяются между собой символом ","(запятая), строки таблицы отделяются друг от друга символом ";" (точка с запятой). После последней клетки идет символ "." (точка). За каждым из этих символов может немедленно следовать один перевод строки, который должен игнорироваться. Другие переводы строки во файле не встречаются.

Если в значении ячейки встречается один из символов ",", ";", ".'"или "\", то в файл записывается два символа – сначала "\", а затем данный символ. Соответственно, запятая, точка с запятой и точка, которые идут непосредственно после "\", не являются разделителями значений ячеек. В частности, после них не может следовать перевода строки.

Каждая ячейка относится к одному из трех типов: числовая, строковая, пустая. Пустая ячейка – это ячейка, значение которой является пустой строкой. Числовая ячейка содержит целое число из диапазона от -32768 до 32767 включительно. Число должно быть записано без ведущих нулей и лишних знаков "+" или "-" (знак "-'" должен быть только у отрицательных чисел, причем ровно один). Любая другая ячейка относится к строковому типу. Так, например, к строковому типу относятся ячейки, содержащие следующие значения: 01 (включает ведущий нуль), 55000 (не входит в указанный диапазон), а также ячейка, содержащая один символ "пробел".

Столбец таблицы называется пустым, если все ячейки, которые он содержит – пустые. Столбец таблицы называется числовым, если он содержит только числовые и пустые ячейки. В противном случае столбец называется строковым. Требуется для каждого столбца таблицы, начиная с первого, и до последнего непустого, определить, к какому типу он относится.

Входные данные
На вход программы поступает электронная таблица, размер входных данных не превышает 32767 байт.

Выходные данные
Для всех столбцов, начиная с первого, и до последнего непустого столбца, выведите их тип, разделив значения запятыми, и в конце поставьте точку. В качестве типа столбца выведите одно из следующих значений: "EMPTY'', если столбец является пустым, "NUMBER'', если столбец является числовым, "STRING'', если столбец является строковым.

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

Когда-то давно люди решили избрать своих правителей и изгнали верховных магов из королевства. Однако недавно верховные маги Светлых и Темных сил договорились вернуть королевство под свой контроль. Для этого они хотят направить в некоторые города королевства магов, которые возьмут эти и смежные с ними города под свой контроль.

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

Однако, при разработке плана захвата обнаружилось две трудности. Во-первых, выяснилось, что маг согласен принять участие в операции только если все маги, которые будут направлены в королевство, будут представлять ту же силу, что и он. То есть либо все участвующие в захвате маги должны быть светлыми, либо все они должны быть темными. Во-вторых, общее число магов, которые могут быть направлены в королевство не должно превышать K. Единственная надежда верховных магов заключается в том, что K достаточно велико, 2^k >= N.

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

Входные данные
В первой строке вводятся целые числа N и K ( 2≤N≤256, 2^k ≥ N, K≤N).

Следующие N строк содержат по N целых чисел каждая. На i-ой позиции i-ой из этих строк расположено число 0, которое означает, что город не соединен дорогой сам с собой. Для всех j≠i число на j-ой позиции i-ой из этих строк равно 1, если i-ый город соединен с j-ым белой дорогой, и равно 2, если они соединены черной дорогой. Числа в строках разделены пробелами.

Гарантируется, что входные данные корректны, то есть если i-ый город соединен с j-ым белой дорогой, то и j-ый соединен с i-ым белой дорогой, аналогично в случае черных дорог.

Выходные данные
Если захватить королевство при заданных условиях невозможно, выведите единственное число 0. В противном случае в первой строке выведите 1, если удастся захватить королевство с использованием светлых магов, и 2, если требуется использовать черных магов. В следующей строке выведите число L≤K – количество использованных магов. Третья строка должна содержать L целых чисел – номера городов, в которые следует направить магов. Заметьте, что вам не требуется минимизировать L. Если решений несколько, выведите любое.

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

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

Входные данные
В первой строке вводится натуральное число N, не превышающее 100 – количество клиентов.

N строках вводятся времена прихода клиентов – по два числа, обозначающие часы и минуты (часы – от 0 до 23, минуты – от 0 до 59). Времена указаны в порядке возрастания (все времена различны).
Гарантируется, что всех клиентов успеют обслужить до полуночи.

Выходные данные
Требуется вывести N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-го клиента (часы и минуты).

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

Входные данные
В первой строке вводятся времена поездки по первой, второй и третьей линии (до пересадки) в минутах. Все времена – натуральные числа и не превышают 1140 минут. Считается, что пересадка не занимает времени.

Во второй строке вводятся количество поездов на первой линии, на второй линии и на третьей линии – натуральные числа, не превосходящие 100.

В третьей строке вводятся времена отправления поездов первой линии со станции, на которой садится Петя (по два числа на каждый поезд – часы и минуты).

В четвертой строке в том же формате вводятся времена отправления поездов второй линии со станции, на которую Петя делает первую пересадку.

В пятой строке – аналогичное расписание поездов третьей линии со станции, на которую Петя делает вторую пересадку.

Находиться в метро с часу ночи до 6 часов утра запрещается (в 6 часов утра на поезд садиться можно). Расписание движения поездов таково, что Петя может добраться до работы, не выходя из метро.

Выходные данные
Выведите время (часы и минуты), в которое Петя может войти в метро, чтобы добраться до работы за наименьшее время. Если решений несколько, выведите любое из них.