Нумерація дерев
Занумеруємо усі бінарні дерева відповідно до наступної схеми: - Порожнє дерево має номер 0. - Дерево з єдиною вершиною має номер 1. - Усі бінарні дерева з m вершинами мають номери, менші за номери дерев з m + 1 вершинами. - Довільне бінарне дерево з m вершинами, ліве піддерево якого має номер L, а праве R, має номер n тоді і тільки тоді, коли усі дерева з m вершинами у яких номер > n омають одну із властивостей: - ліве піддерево має номер, більший за L, або - ліве піддерево має номер L, а праве піддерево має номер, більший за R. Перші 10 бінарних дерев та 20-е дерево цієї послідовності наведені нижче:
Вам необхідно вивести бінарне дерево за його номером.
Вхідні дані
Складається з декількох тестів. Кожний тест містить одне ціле число n (1 ≤ n ≤ 500,000,000). Останній рядок містить n = 0 і не обробляється. (Зауважте, що таким чином у Вас ніколи не буде виведено порожнє дерево)
Вихідні дані
Для кожного значення n слід вивести рядок, що містить дерево з номером n. Для виводу дерева скористуйтеся наступною схемою:
Дерево без дітей виводити як X. Дерево з лівим піддеревом L і правим R слід виводити у вигляді (L')X(R'), де L' и R' - представлення піддере L та R. Якщо L порожньо, то виводити X(R'). Якщо R порожньо, то виводити (L')X.