Інструкція
Інгрід є керівником великої залізничної станції і, серед інших обов'язків, відповідає за переміщення поїздів по платформах. Станція має один вхід, а також набір перемикачів, які спрямовують поїзди на інші перемикачі та платформи.
Кожен перемикач має один вхід і два виходи, платформи мають один вхід, а вхід станції має один вихід. Кожен вихід підключений до одного входу і навпаки. Будь-який перемикач і будь-яка платформа досяжні з входу станції.
Платформи закінчуються тупиками. Вважайте, що поїзди одразу ж після прибуття до них зникають з платформи.
Щоранку Інгрід переглядає розклад і записує інструкції для перемикачів: коли і який тумблер перемикати. Вона хотіла б автоматизувати цей процес, щоб зекономити багато часу.
Вхідні дані
Перший рядок містить загальну кількість перемикачів і платформ 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.
Приклад
Нижче наведено часовий графік для першого прикладу.
