#include < iostream >
using namespace std;

struct tree {
    tree * right;
    tree * middle;
    tree * left;
    int data1;
    int data2;
    tree * parent;
};

void Output(tree * root) {
    if (root -> right != NULL) {
        Output(root -> right);
    }
    cout << " " << root -> data1 << " ";

    if (root -> middle != NULL) {
        Output(root -> middle);
    }

    if (root -> data2 != -1) {
        cout << " " << root -> data2 << " ";
    }

    if (root -> left != NULL) {
        Output(root -> left);
    }
}

void Input_mid(tree * & point, int num);
void Input_right(tree * & point, int num);

void Order(tree * root, tree * point) {
    if (point == root -> right) {
        if (root -> data2 == -1) {
            root -> data2 = root -> data1;
            root -> data1 = point -> data1;
            root -> left = root -> middle;
            root -> middle = point -> middle;
            point -> middle = NULL;
            root -> middle -> parent = root;
            root -> right = point -> right;
            point -> right = NULL;
            root -> right -> parent = root;
            delete(point);
            return;
        }

        if (root -> data2 != -1) {
            tree * point;
            tree * point2;
            tree * point3;
            tree * point4;

            point2 = root -> left;
            point = root -> middle;
            point3 = point -> right;
            point4 = point -> middle;

            Input_mid(root, root -> data2);
            root -> middle -> right = point;
            root -> middle -> middle = point2;
            root -> data2 = -1;

            Input_right(root, point -> data1);
            root -> right -> right = point3;
            root -> right -> middle = point4;
            root -> left = NULL;
            delete(point);

        }
    }

    if (point == root -> middle) {
        if (root -> data2 == -1) {
            root -> data2 = point -> data1;
            root -> left = root -> middle -> middle;
            root -> middle -> middle = NULL;
            root -> middle = point -> right;
            point -> right = NULL;
            root -> middle -> parent = root;
            root -> left -> parent = root;
            delete(point);
            return;
        }

        if (root -> data2 != -1) {
            tree * point;
            tree * point2;
            tree * point3;
            tree * point4;

            point = root -> right;
            point2 = root -> left;
            point3 = point -> right;
            point4 = point -> middle;

            Input_right(root, root -> data1);
            Input_mid(root, root -> data2);
            root -> data2 = -1;
            root -> data1 = point -> data1;
            root -> right -> right = point;
            root -> right -> middle = point3;
            root -> middle -> right = point4;
            root -> middle -> middle = point2;
            root -> left = NULL;
        }
    }

    if (point == root -> left) {
        tree * point;
        tree * point2;
        tree * point3;
        tree * point4;

        point = root -> right;
        point2 = root -> middle;

        Input_right(root, root -> data1);
        root -> data1 = root -> data2;
        root -> right -> right = point;
        root -> right -> middle = point2;
        root -> middle = NULL;
        root -> middle = root -> left;
        root -> left = NULL;
        root -> data2 = -1;
    }
}

void Input_init(tree * & point, int num) {
    point -> data1 = num;
    point -> data2 = -1;
    point -> right = NULL;
    point -> middle = NULL;
    point -> left = NULL;
    point -> parent = NULL;
}

void Input_right(tree * & point, int num) {
    point -> right = new tree;
    point -> right -> data1 = num;
    point -> right -> data2 = -1;
    point -> right -> right = NULL;
    point -> right -> middle = NULL;
    point -> right -> left = NULL;
    point -> right -> parent = point;
}
void Input_mid(tree * & point, int num) {
    point -> middle = new tree;
    point -> middle -> data1 = num;
    point -> middle -> data2 = -1;
    point -> middle -> right = NULL;
    point -> middle -> middle = NULL;
    point -> middle -> left = NULL;
    point -> middle -> parent = point;
}

void Input(tree * & point, int number, tree * & prim) {
    if ((number <= point -> data1) && (point -> data2 == -1) && (point -> right == NULL)) {
        point -> data2 = point -> data1;
        point -> data1 = number;
        return;
    }

    if ((number > point -> data1) && (point -> data2 == -1) && (point -> right == NULL)) {
        point -> data2 = number;
        return;
    }

    if ((point -> right != NULL) && (point -> data1 >= number)) {
        Input(point -> right, number, prim);
        return;
    }

    if ((point -> middle != NULL) && (point -> data2 >= number) && (point -> data1 < number)) {
        Input(point -> middle, number, prim);
        return;
    }

    if ((point -> middle != NULL) && (point -> data2 == -1) && (point -> data1 < number)) {
        Input(point -> middle, number, prim);
        return;
    }

    if ((point -> left != NULL) && (point -> data2 < number)) {
        Input(point -> left, number, prim);
        return;
    }

    if ((number <= point -> data1) && (point -> data2 != -1) && (point -> right == NULL)) {
        Input_right(point, number);
        Input_mid(point, point -> data2);
        point -> data2 = -1;

        if (point -> parent != NULL) {
            Order(point -> parent, point);
        }
        return;
    }

    if ((number > point -> data1) && (number <= point -> data2)) {
        Input_right(point, point -> data1);
        Input_mid(point, point -> data2);
        point -> data2 = -1;
        point -> data1 = number;

        if (point -> parent != NULL) {
            Order(point -> parent, point);
        }
        return;
    }

    if ((number > point -> data2) && (point -> data2 != -1)) {
        Input_right(point, point -> data1);
        Input_mid(point, number);
        point -> data1 = point -> data2;
        point -> data2 = -1;

        if (point -> parent != NULL) {
            Order(point -> parent, point);
        }
        return;
    }
}

int main() {
    tree root, * P, * P1;
    P1 = P = & root;
    int num;
    cout << "Input number - ";
    cin >> num;
    Input_init(P, num);

    while (num != 0) {
        cout << "Input number - ";
        cin >> num;

        if (num < 0) {
            num = num * -1;
        }
        if (num != 0) {
            Input(P, num, P1);
        }
    }

    Output(P);
    return 0;
}