--->
2 задач
<---
Источники
Ежегодно в Санкт-Петербурге, Барнауле и некоторых городах ближнего зарубежья проходят соревнования по программированию. Эти соревнования проходят в рамках студенческого чемпионата мира по программированию, организованного одной из самых авторитетных ассоциаций АСМ (Association for Computing Machinery). На этих соревнованиях проходит отбор команд с Северо-Восточного Европейского Региона NЕЕRС (North-Eastern European Regional Contest). Ежегодно перед организаторами соревнований встает проблема определения команд, которые будут приглашены к участию в финале чемпионата мира по программированию. По новым правилам в финал проходят не более N команд, представляющих NEERC. Кроме этого, от одного вуза не может проходить более чем k команд. При этот из всех таких множеств выбирается то, в котором сумма мест занятых этими командами в полуфинальных соревнованиях минимальная возможная. Ваша задача по итоговому протоколу полуфинальных соревнований и числам N и k определить, какие команды будут приглашены к участию в финале чемпионата мира.
В первой сроке входного файла находится три натуральных числа Р (1 ≤ P ≤ 100000) — количество команд, принявших участие в полуфинале, N (1 ≤ N ≤ P ) и k (1 ≤ k ≤ P ) . В следующих P строках, по одному в строке перечислены названия университетов, команды которых заняли соответствующие места. Название университета содержит строчные и прописные латинские буквы и пробелы. Длина названия университета не превышает 30 символов. В следующей строке перечислены номера команд соответствующих университетов. Таким образам если название университета записано в i -той строке (2 ≤ i ≤ P + 1) , то эта команда заняла i - 1 место на полуфинале и имеет номер, записанный на i - 1 месте в P + 2 строке.
В выходной файл выведите названия команд, приглашенных к участию в финале чемпионата мира по программированию, упорядоченных по месту, занятому на полуфинале. В качестве названия команды выведите название университета и через пробел #номер команды.
9 5 2 Fantasy University Crazy University Fantasy University Fantasy University Very Good U Good U Very Good U Crazy University Good U 1 1 2 3 2 1 1 2 2
Fantasy University #1 Crazy University #1 Fantasy University #2 Very Good U #2 Good U #1
В стране Байтландии есть n городов, соединенных дорогами. Каждая дорога двухсторонняя и имеет некоторую длину. Также, в стране есть две партии — одна выступает за то, что вилку необходимо держать во время еды в левой руке, другая — за то, что вилку необходимо держать в правой руке. В каждый момент времени каждый из городов поддерживает только одну партию. Вот только время от времени в городах происходят перевороты и в одном из городов поддерживаемая партия меняется на противоположную.
Правительство Байтландии поручило Вам написать программу, которая бы в каждый момент времени оценивала стабильность политической ситуации в стране. Согласно математической модели, разработанной ведущими учеными Байтландии, стабильность зависит от того, насколько близко находятся города, поддерживающие одну и ту же партию, поскольку чем ближе они, чем больше вероятность того, что они могут объединиться в коалицию.
Поэтому программа, написанная Вами, должна по информации о всех городах, дорогах и происходящих переворотах находить, после каждого переворота, два города, поддерживающих одну партию, и находящихся на наименьшем расстоянии друг от друга.
Первая строка входного файла содержит три целых числа n, m и k (1 ≤ n, m, k ≤ 100000) — количество городов, дорог и переворотов соответственно.
Вторая строка содержит строку s длиной n, описывающую политическую ситуацию в стране на момент начала наблюдения. Символ L на i-ой позиции означает, что город номер i поддерживает партию, выступающую за то, что вилку необходимо держать в левой руке, символ R — в правой.
Следующие m строк содержат по три целых числа ai, bi и li (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ li ≤ 109) — номера городов, которые соединены i-ой дорогой и ее длина. Каждая пара городов соединена не более, чем одной дорогой.
В последней строке содержится k чисел --- номера городов cj (1 ≤ cj ≤ n), в которых происходили перевороты в порядке их происшествия. Поскольку все города достаточно консервативны, то в каждом городе произошло не более одного переворота, то есть все cj различны.
В выходной файл выведите k + 1 отчет о ближайших городах, которые могут объединиться в коалицию. Первое описание должно соответствовать началу наблюдения, каждое следующее — после очередного переворота в одном из городов.
Каждое описание должно быть выведено на отдельной строке и содержать три целых числа di, xi и yi — минимальное расстояния между городами, поддерживающими одну партию и номера этих городов, соответственно. Если таких пар несколько, выведите любую. Гарантируется, что хотя бы одна такая пара всегда существует.
n ≤ 100. Решение оценивается в 30 баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.
5 6 4 LRLRL 1 4 1 2 3 2 3 4 3 4 5 4 2 5 5 2 4 6 1 4 3 5
4 1 3 1 1 4 3 3 4 2 2 3 2 2 3