eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Инструкция

Инструкция

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

Каждый переключатель имеет один вход и два выхода, платформы имеют один вход, вход станции имеет один выход. Каждый выход подключен к одному входу и наоборот. Любой переключатель и любая платформа достижимы со входа станции.

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

prb7500.gif

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

Вхідні дані

Первая строка содержит общее количество переключателей и платформ n (3n51) на станции.

Строка номер i из следующих n строк описывает переключатель или платформу с индексом i. Описание начинается символом p для платформы или s для переключателя. Следующее число q[i] (0q[i] < i) содержит номер переключателя, к входной дорожке которого он подсоединен, или 0 если он подключен ко входу станции. Описание платформы также содержит уникальную строчную английскую букву - идентификатор платформы.

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

Следующая строка содержит количество поездов m (1m1000) в расписании.

Каждая из следующих m строк содержит целое число a[i] (0a[i]10 000, a[i] > a[i-1]) - время в минутах, когда поезд прибывает на вход станции, и буква p[i] - идентификатор платформы назначения для этого поезда.

Вихідні дані

В первой строке выведите целое число c - количество команд изменения переключателей. Для каждой команды выведите два целых числа s[i] и t[i] (1s[i]n, 0t[i]10^9) - номер переключателя и время когда его следует переключить. Считайте что переключение происходит между минутами t[i] - 1 и t[i].

Выводите команды в порядке не возрастания времени. Количество команд не должно превосходить 100 000.

Пример

Ниже приведен временной график для первого примера.

prb7500_1.gif

Приклад

Вхідні дані #1
7
s 0
s 1
s 1
p 2 a
p 2 b
p 3 c
p 3 d
5
0 a
1 c
3 b
4 a
5 d
Вихідні дані #1
6
1 2
1 4
2 5
2 6
1 6
3 7
Вхідні дані #2
5
s 0
p 1 y
s 1
p 3 z
p 3 x
3
7 y
8 y
15 y
Вихідні дані #2
0
Вхідні дані #3
3
s 0
p 1 y
p 1 z
3
7 y
8 y
10 y
Вихідні дані #3
5
1 1
1 2
1 2
1 3
1 200
Джерело 2014 ACM NEERC, Northern Subregion, Ноябрь 8, Задача I