Дерева

Двоїчне дерево пошуку (BST) — це двійкове дерево, в якому кожен вузол має значення, і організоване так, що для будь-якого вузла всі значення в його лівому піддереві менші за значення вузла, а всі значення в його правому піддереві більші за значення вузла.

Щоб побудувати BST з послідовності різних цілих чисел, використовується наступна процедура. Перше число стає коренем дерева. Потім розглядається друге число в послідовності. Якщо воно менше за значення кореневого вузла, то стає лівою дитиною. Інакше воно стає правою дитиною. Наступні елементи в послідовності рухаються вниз або вліво, або вправо таким же чином залежно від порівняння з попередніми вузлами, починаючи з кореня і просуваючись вниз по дереву. Новий вузол вставляється (як листок) у частково побудоване дерево, коли досягає відсутнього піддерева в певному напрямку руху.

Наприклад, BST, згенероване послідовністю [2, 1, 4, 3], будується, як показано нижче, коли числа вставляються.

Рисунок 1: Генерація BST

Дерево (d) на Рисунку 1 також може бути згенероване двома іншими послідовностями: [2, 4, 3, 1] та [2, 4, 1, 3].

Такі послідовності можна порівнювати за лексикографічним порядком, де порівняння відбувається зліва направо, і елементи на відповідних позиціях порівнюються за їх числовими значеннями. Результат для [2, 1, 4, 3], [2, 4, 3, 1] та [2, 4, 1, 3] такий, використовуючи "<" для позначення цього лексикографічного порядку між послідовностями: [2, 1, 4, 3] < [2, 4, 1, 3] < [2, 4, 3, 1].

Для дерева (d) на Рисунку 1 лексикографічно найменша послідовність — це [2, 1, 4, 3].

Напишіть програму, яка зчитуватиме представлення дерева і генеруватиме лексикографічно найменшу послідовність різних додатних цілих чисел, яка згенерує це дерево. Зверніть увагу, що для дерева з n вузлами ця послідовність буде перестановкою чисел від 1 до n.

Для введення нашої задачі ми представляємо (рекурсивно) структуру дерева наступним чином:

1. Один вузол (листок) є деревом:

   • ()

2. Якщо TL та TR є деревами, то наступні також є деревами:

   • (TL,)

   • (,TR)

   • (TL,TR)

Вхідні дані

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

Вихідні дані

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

Приклади