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

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

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

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

Входные данные

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

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

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

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

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

Выходные данные

В первой строке выведите целое число c - количество команд изменения переключателей. Для каждой команды выведите два целых числа si и ti (1 ≤ si ≤ n, 0 ≤ ti ≤ 109) - номер переключателя и время когда его следует переключить. Считайте что переключение происходит между минутами ti - 1 и ti.

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

Пример

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