---

#include <stdio.h>
#include <stdlib.h>

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
};


/* Добавление элемента в дерево */
struct tree *add(struct tree *T, int x)
{
    if (T == NULL) {
        T = malloc(sizeof(struct tree));

        T->data = x;
        T->left = NULL;
        T->right = NULL;

        return T;
    }

    if (x < T->data)
        T->left = add(T->left, x);
    else if (x > T->data)
        T->right = add(T->right, x);

    /* если x == T->data, дубликат пропускаем */

    return T;
}


/* Печать дерева по возрастанию */
void print_tree(struct tree *T)
{
    if (T == NULL)
        return;

    print_tree(T->left);

    printf("%d ", T->data);

    print_tree(T->right);
}


/* Удаление одной вершины */
struct tree *delete_node(struct tree *T, int x)
{
    if (T == NULL)
        return NULL;

    if (x < T->data) {
        T->left = delete_node(T->left, x);
    }
    else if (x > T->data) {
        T->right = delete_node(T->right, x);
    }
    else {
        /* нашли вершину */

        /* нет левого сына */
        if (T->left == NULL) {
            struct tree *p = T->right;
            free(T);
            return p;
        }

        /* нет правого сына */
        if (T->right == NULL) {
            struct tree *p = T->left;
            free(T);
            return p;
        }

        /*
         * Есть оба сына.
         * Находим минимальный элемент
         * в правом поддереве.
         */
        struct tree *p = T->right;

        while (p->left != NULL)
            p = p->left;

        T->data = p->data;

        T->right = delete_node(T->right, p->data);
    }

    return T;
}


/* Полное удаление дерева */
void delete_tree(struct tree *T)
{
    if (T == NULL)
        return;

    delete_tree(T->left);
    delete_tree(T->right);

    free(T);
}


int main(void)
{
    int x;

    while (scanf("%d", &x) == 1) {

        /* начало новой последовательности */
        if (x == 0)
            continue;

        struct tree *T = NULL;

        int first = x;
        int last = x;

        T = add(T, x);

        int eof = 0;

        /* читаем оставшуюся последовательность */
        while (1) {

            if (scanf("%d", &x) != 1) {
                eof = 1;
                break;
            }

            if (x == 0)
                break;

            last = x;

            T = add(T, x);
        }


        /* первое распечатывание */
        print_tree(T);
        printf("0\n");


        /* удаляем первый элемент */
        T = delete_node(T, first);

        /* если first == last, второй раз удалять не надо */
        if (last != first)
            T = delete_node(T, last);


        /* второе распечатывание */
        print_tree(T);
        printf("0\n");


        /* освобождаем всю память */
        delete_tree(T);

        if (eof)
            break;
    }

    return 0;
}