Китайская классика
Таро, ученик средней школы, работает над своим домашним заданием. Сегодняшнее задание — читать китайские классические тексты.
Как вы знаете, японский язык использует (в основном) те же китайские иероглифы, но порядок слов немного отличается. Поэтому была изобретена нотация, называемая "возвратные знаки", чтобы читать китайские классические тексты в порядке, похожем на японский язык.
Существует два основных типа возвратных знаков: знак 'Re' и прыжковые знаки. Также есть несколько прыжковых знаков, таких как знаки один-два-три, верх-середина-низ. Знаки прикрепляются к буквам, чтобы описать порядок чтения каждой буквы в китайском классическом тексте. Рисунок 1 — это пример китайского классического текста с аннотацией возвратными знаками, которые представлены маленькими буквами в нижнем левом углу больших китайских букв.
Рисунок 1: китайский классический текст
Таро обобщил концепцию прыжковых знаков и сформулировал правила для чтения китайских классических текстов с возвратными знаками следующим образом. Ваша задача — помочь Таро, написав программу, которая интерпретирует китайские классические тексты с возвратными знаками, следуя его правилам, и выводит порядок чтения каждой буквы. Когда на каждом шаге применимы два (или более) правила, сначала применяется последнее в списке ниже, затем предыдущее.
В основном буквы читаются сверху вниз, т.е. первая буква должна быть прочитана (или пропущена) первой, и после того, как i-я буква прочитана или пропущена, следующей читается (i+1)-я буква.
Каждое прыжковое обозначение имеет тип (представленный строкой, состоящей из строчных букв) и номер (представленный положительным целым числом). Буква с прыжковым знаком, номер которого 2 или больше, должна быть пропущена.
Когда i-я буква с прыжковым знаком типа t, номер n читается, и когда существует непрочитанная буква L на позиции меньше i, которая имеет прыжковый знак типа t, номер n+1, тогда L должна быть прочитана следующей. Если такой буквы L нет, читается (k+1)-я буква, где k — индекс последней прочитанной буквы с прыжковым знаком типа t, номер 1.
Буква с знаком 'Re' должна быть пропущена.
Когда i-я буква читается и (i-1)-я буква имеет знак 'Re', тогда (i-1)-я буква должна быть прочитана следующей.
Ни одна буква не может быть прочитана дважды или более. Как только буква прочитана, она должна быть пропущена в последующих шагах.
Если ни одна буква не может быть прочитана следующей, завершите чтение.
Рассмотрим первый случай из примера ввода. Мы начинаем чтение с первой буквы из-за правила 1. Однако, поскольку первая буква имеет прыжковый знак 'onetwo2', мы должны следовать правилу 2 и пропустить букву. Поэтому вторая буква, которая не имеет возвратного знака, будет прочитана первой.
Затем будет прочитана третья буква. Третья буква имеет прыжковый знак 'onetwo1', поэтому мы должны следовать правилу 3 и прочитать букву с прыжковым знаком 'onetwo2' следующей, если она существует. Первая буква имеет такой знак, поэтому она будет прочитана третьей. Аналогично, пятая буква читается четвертой, а затем читается шестая буква.
Хотя у нас есть две буквы с одинаковым прыжковым знаком 'onetwo2', мы не должны учитывать первую букву, которая уже была прочитана, и должны прочитать четвертую букву. Теперь мы прочитали все шесть букв, и ни одна буква не может быть прочитана следующей, поэтому мы завершаем чтение. Мы прочитали вторую, третью, первую, пятую, шестую и четвертую буквы в этом порядке, поэтому вывод будет 2 3 1 5 6 4.
Входные данные
Ввод содержит несколько наборов данных. Каждый набор данных представлен в следующем формате:
N mark_1 ... mark_N
N, положительное целое число (1 ≤ N ≤ 10000), означает количество букв в китайском классическом тексте. mark_i обозначает возвратные знаки, прикрепленные к i-й букве.
Знак 'Re' представлен одной буквой, а именно, 'v' (кавычки для ясности). Описание прыжкового знака — это простая конкатенация его типа, указанного одной или несколькими строчными буквами, и положительного целого числа. Обратите внимание, что каждая буква имеет не более одного прыжкового знака и не более одного знака 'Re'. Когда одна и та же буква имеет оба типа возвратных знаков, описание прыжкового знака идет первым, за ним следует 'v' для знака 'Re'. Вы можете предположить, что это происходит только на прыжковых знаках с номером 1.
Если i-я буква не имеет возвратного знака, mark_i — '-' (кавычки для ясности). Длина mark_i никогда не превышает 20.
Вы можете предположить, что ввод хорошо сформирован, то есть существует ровно один порядок чтения, который следует вышеуказанным правилам. И в этом порядке каждая буква читается ровно один раз.
Вы также можете предположить, что N-я буква не имеет знака 'Re'.
Ввод заканчивается, когда N = 0. Ваша программа не должна выводить ничего для этого случая.
Выходные данные
Для каждого набора данных вы должны вывести N строк. Первая строка должна содержать индекс буквы, которая должна быть прочитана первой, вторая строка — для буквы, которая должна быть прочитана второй, и так далее. Все индексы основаны на 1.