Задача №112793. Партии
В стране Байтландии есть 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