Китайська класика#3595

Китайська класика

30 секунд

256 мегабайтів

Легка

Таро, учень середньої школи, працює над своїм домашнім завданням. Сьогоднішнє завдання — читати китайські класичні тексти.

Відомо, що японська мова використовує (переважно) ті ж китайські ієрогліфи, але порядок слів трохи відрізняється. Тому була винайдена нотація, яка називається "повертаючі знаки", щоб читати китайські класичні тексти в порядку, схожому на японську мову.

Існує два основних типи повертаючих знаків: знак 'Re' і стрибкові знаки. Також є кілька стрибкових знаків, таких як знаки один-два-три, знаки верх-середина-низ. Знаки прикріплюються до літер, щоб описати порядок читання кожної літери в китайському класичному тексті. Рисунок 1 є прикладом китайського класичного тексту з анотацією повертаючими знаками, які є маленькими літерами внизу зліва від великих китайських літер.

Рисунок 1: китайський класичний текст

Таро узагальнив концепцію стрибкових знаків і підсумував правила читання китайських класичних текстів з повертаючими знаками, як зазначено нижче. Ваше завдання — допомогти Таро, написавши програму, яка інтерпретує китайські класичні тексти з повертаючими знаками, дотримуючись його правил, і виводить порядок читання кожної літери. Коли два (або більше) правила застосовні на кожному кроці, спочатку застосовується останнє в списку нижче, потім перше.

В основному літери читаються вниз від верху до низу, тобто перша літера повинна бути прочитана (або пропущена) першою, і після того, як $i$ -та літера прочитана або пропущена, $(i + 1)$ (i+1)-та літера читається наступною.
Кожен стрибковий знак має тип (представлений рядком, що складається з малих літер) і число (представлене додатним цілим числом). Літера зі стрибковим знаком, число якого $2$ або більше, повинна бути пропущена.
Коли $i$ -та літера зі стрибковим знаком типу $t$ , число $n$ прочитана, і коли існує непрочитана літера $L$ на позиції менше $i$ , яка має стрибковий знак типу $t$ , число $n + 1$ n+1, тоді $L$ повинна бути прочитана наступною. Якщо такої літери $L$ немає, читається $(k + 1)$ (k+1)-та літера, де $k$ — індекс останньої прочитаної літери зі стрибковим знаком типу $t$ , число $1$ .
Літера зі знаком 'Re' повинна бути пропущена.
Коли $i$ -та літера прочитана і $(i - 1)$ (i-1)-та літера має знак 'Re', тоді $(i - 1)$ (i-1)-та літера повинна бути прочитана наступною.
Жодна літера не може бути прочитана двічі або більше. Після того, як літера прочитана, вона повинна бути пропущена в наступних кроках.
Якщо жодна літера не може бути прочитана наступною, завершити читання.

Розглянемо перший випадок з прикладу вхідних даних. Ми починаємо читання з першої літери через правило $1$ . Однак, оскільки перша літера має стрибковий знак 'onetwo2', ми повинні дотримуватися правила $2$ і пропустити цю літеру. Тому друга літера, яка не має повертаючого знака, буде прочитана першою.

Потім буде прочитана третя літера. Третя літера має стрибковий знак 'onetwo1', тому ми повинні дотримуватися правила $3$ і прочитати літеру зі стрибковим знаком 'onetwo2' наступною, якщо така існує. Перша літера має точний стрибковий знак, тому вона буде прочитана третьою. Аналогічно, п'ята літера читається четвертою, а потім читається шоста літера.

Хоча у нас є дві літери, які мають однаковий стрибковий знак 'onetwo2', ми не повинні враховувати першу літеру, яка вже була прочитана, і повинні прочитати четверту літеру. Тепер ми прочитали всі шість літер, і жодна літера не може бути прочитана наступною, тому ми завершуємо читання. Ми прочитали другу, третю, першу, п'яту, шосту і четверту літери в цьому порядку, тому вихід — $2$ $3$ $1$ $5$ $6$ $4$ .

Вхідні дані

Вхід містить кілька наборів даних. Кожен набір даних подається у наступному форматі:

$N$ $ma r k_{1}$ mark_1 $\dots$ $ma r k_{N}$ mark_N

$N$ , додатне ціле число ( $1 \leq N \leq 10000$ 1 \le N \le 10000), означає кількість літер у китайському класичному тексті. $ma r k_{i}$ mark_i позначає повертаючі знаки, прикріплені до $i$ -тої літери.

Знак 'Re' представлений однією літерою, а саме, 'v' (лапки для ясності). Опис стрибкового знака — це просте з'єднання його типу, визначеного однією або кількома малими літерами, і додатного цілого числа. Зверніть увагу, що кожна літера має не більше одного стрибкового знака і не більше одного знака 'Re'. Коли одна і та ж літера має обидва типи повертаючих знаків, опис стрибкового знака йде першим, за ним 'v' для знака 'Re'. Ви можете припустити, що це відбувається лише на стрибкових знаках з числом $1$ .

Якщо $i$ -та літера не має повертаючого знака, $ma r k_{i}$ mark_i — '-' (лапки для ясності). Довжина $ma r k_{i}$ mark_i ніколи не перевищує $20$ .

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

Ви також можете припустити, що $N$ -та літера не має знака 'Re'.

Вхід закінчується, коли $N = 0$ N = 0. Ваша програма не повинна нічого виводити для цього випадку.

Вихідні дані

Для кожного набору даних ви повинні вивести $N$ рядків. Перший рядок повинен містити індекс літери, яка буде прочитана першою, другий рядок для літери, яка буде прочитана другою, і так далі. Всі індекси є $1$ -базованими.

Приклади

Приклад 1