Инструкция
Ингрид является главой большой железнодорожной станции, и помимо прочих обязанностей, отвечает за перемещение поездов по платформам. Станция имеет один вход. Имеется набор переключателей, которые направляют поезда на другие переключатели и платформы.
Каждый переключатель имеет один вход и два выхода, платформы имеют один вход, вход станции имеет один выход. Каждый выход подключен к одному входу и наоборот. Любой переключатель и любая платформа достижимы со входа станции.
Платформы заканчиваются тупиками. Считайте, что поезда сразу же после прибытия к ним исчезают с платформы.
Каждое утро Ингрид смотрит на расписание и записывает инструкции переключений: когда и какой тумблер переключать. Она хотела бы автоматизировать этот процесс, чтобы сэкономить много времени.
Входные данные
Первая строка содержит общее количество переключателей и платформ n (3 ≤ n ≤ 51) на станции.
Строка номер i из следующих n строк описывает переключатель или платформу с индексом i. Описание начинается символом p для платформы или s для переключателя. Следующее число q[i] (0 ≤ q[i] < i) содержит номер переключателя, к входной дорожке которого он подсоединен, или 0 если он подключен ко входу станции. Описание платформы также содержит уникальную строчную английскую букву - идентификатор платформы.
Поездам необходима ровно одна минута, чтобы переместиться между двумя подключенными коммутаторами или коммутатором и платформой. Утром каждый тумблер переключается таким образом, что поезд будет проходить к одной из двух исходящих дорожек, подключенных к коммутатору / платформе, с более низким номером.
Следующая строка содержит количество поездов m (1 ≤ m ≤ 1000) в расписании.
Каждая из следующих m строк содержит целое число a[i] (0 ≤ a[i] ≤ 10 000, a[i] > a[i-1]) - время в минутах, когда поезд прибывает на вход станции, и буква p[i] - идентификатор платформы назначения для этого поезда.
Выходные данные
В первой строке выведите целое число c - количество команд изменения переключателей. Для каждой команды выведите два целых числа s[i] и t[i] (1 ≤ s[i] ≤ n, 0 ≤ t[i] ≤ 10^9) - номер переключателя и время когда его следует переключить. Считайте что переключение происходит между минутами t[i] - 1 и t[i].
Выводите команды в порядке не возрастания времени. Количество команд не должно превосходить 100 000.
Пример
Ниже приведен временной график для первого примера.
