Однорідні піддерева

Визначимо Однорідне дерево як таке, в якому всі вузли на певному рівні (тобто на однаковій відстані від кореня) мають однаковий ступінь (тобто однакову кількість дітей). Оскільки всі вузли на певному рівні мають однакову кількість дітей, однорідне дерево можна описати як список цілих чисел, що вказують на кількість дітей на кожному рівні. Наприклад, список [2 3 5 0] представляє дерево, де корінь має 2 дітей, кожна дитина кореня має 3 дітей, кожен онук має 5 дітей, а кожен праонук не має дітей, тобто є листком.

Для цілей цієї задачі, перевизначимо Піддерево як зв'язний підграф дерева, що включає корінь дерева. Це трохи відрізняється від звичайного визначення Піддерева.

Маючи опис дерева, знайдіть всі унікальні Однорідні Піддерева цього дерева. Наприклад, ось дерево та всі його унікальні однорідні піддерева:

Вхідні дані

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

Вихідні дані

Для кожного тестового випадку виведіть кожне унікальне однорідне піддерево даного дерева у вигляді списку цілих чисел, одне піддерево (і, отже, один список) на рядок. Друкуйте один пробіл між цілими числами, і жодних пробілів більше ніде. Не друкуйте жодних порожніх рядків між списками або між тестовими випадками. Друкуйте списки для даного тестового випадку, відсортовані за першим елементом, потім другим, потім третім і так далі.