Інструкція#7500

Інструкція

1 секунда

128 мегабайтів

Складна

Інгрід є керівником великої залізничної станції і, серед інших обов'язків, відповідає за переміщення поїздів по платформах. Станція має один вхід, а також набір перемикачів, які спрямовують поїзди на інші перемикачі та платформи.

Кожен перемикач має один вхід і два виходи, платформи мають один вхід, а вхід станції має один вихід. Кожен вихід підключений до одного входу і навпаки. Будь-який перемикач і будь-яка платформа досяжні з входу станції.

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

Щоранку Інгрід переглядає розклад і записує інструкції для перемикачів: коли і який перемикач перемикати. Вона хотіла б автоматизувати цей процес, щоб зекономити багато часу.

Вхідні дані

Перший рядок містить загальну кількість перемикачів і платформ $n$ ( $3 \leq n \leq 51$ 3 \leq n \leq 51) на станції.

Рядок номер $i$ з наступних $n$ рядків описує перемикач або платформу з індексом $i$ . Опис починається символом p для платформи або s для перемикача. Наступне число $q_{i}$ q_i ( $0 \leq q_{i} < i$ 0 \leq q_i < i) вказує номер перемикача, до вхідної доріжки якого він підключений, або $0$ , якщо він підключений до входу станції. Опис платформи також містить унікальну строчну англійську букву — ідентифікатор платформи.

Поїздам необхідна рівно одна хвилина, щоб переміститися між двома підключеними перемикачами або перемикачем і платформою. Вранці кожен перемикач налаштований так, щоб поїзд проходив до однієї з двох вихідних доріжок, підключених до перемикача або платформи, з меншим номером.

Наступний рядок містить кількість поїздів $m$ ( $1 \leq m \leq 1000$ 1 \leq m \leq 1000) у розкладі.

Кожен з наступних $m$ рядків містить ціле число $a_{i}$ a_i ( $0 \leq a_{i} \leq 10000$ 0 \leq a_i \leq 10\,000, $a_{i} > a_{i - 1}$ a_i > a_{i-1}) — час у хвилинах, коли поїзд прибуває на вхід станції, і букву $p_{i}$ p_i — ідентифікатор платформи призначення для цього поїзда.

Вихідні дані

У першому рядку виведіть ціле число $c$ — кількість команд зміни перемикачів. Для кожної команди виведіть два цілі числа $s_{i}$ s_i і $t_{i}$ t_i ( $1 \leq s_{i} \leq n$ 1 \leq s_i \leq n, $0 \leq t_{i} \leq 1 0^{9}$ 0 \leq t_i \leq 10^9) — номер перемикача і час, коли його слід перемкнути. Вважайте, що перемикання відбувається між хвилинами $t_{i} - 1$ t_i - 1 і $t_{i}$ t_i.

Виводьте команди в порядку не спадання часу. Кількість команд не повинна перевищувати $100000$ .

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

Нижче наведено часовий графік для першого прикладу.