#include <iostream>
#include <stdio.h>
using namespace std;
struct Node
{
    int data;
    int height;
    Node* left;
    Node* right;
};
int max(int a, int b)
{
    return a > b ? a : b;
}
int height(Node* root)
{
    if (root != NULL)
        return root->height;
    return 0;
}
void bsearsh(Node* root)
{
    if (root == 0)
        return;
    bsearsh(root->left);
    bsearsh(root->right);
    printf("%d\n", root->data);
}
void fsearsh(Node* root)
{
    if (root == 0)
        return;
    printf("%d\n", root->data);
    fsearsh(root->left);
    fsearsh(root->right);
}
Node* leftLeftRotation(Node* root)
{
    Node* k;
    k = root->left;
    root->left = k->right;
    k->right = root;
    root->height = max(height(root->left), height(root->right)) + 1;
    k->height = max(height(k->left), root->height) + 1;
    return k;
}
Node* rightRightRotation(Node* root)
{
    Node* k;
    k = root->right;
    root->right = k->left;
    k->left = root;
    root->height = max(height(root->left), height(root->right)) + 1;
    k->height = max(height(k->right), root->height) + 1;
    return k;
}
Node* leftRightRotation(Node* root)
{
    root->left = rightRightRotation(root->left);
    return leftLeftRotation(root);
}
Node* rightLeftRotation(Node* root)
{
    root->right = leftLeftRotation(root->right);
    return rightRightRotation(root);
}
Node* insert(Node*& root, int x)
{
    if (root == 0)
    {
        root = new Node;
        root->left = 0;
        root->right = 0;
        root->height = 0;
        root->data = x;
    }
    else if (x < root->data)
    {
        root->left = insert(root->left, x);
        if (height(root->left) - height(root->right) == 2)
        {
            if (x < root->left->data)
                root = leftLeftRotation(root);
            else
                root = leftRightRotation(root);
        }
    }
    else if (x > root->data)
    {
        root->right = insert(root->right, x);
        if (height(root->right) - height(root->left) == 2)
        {
            if (x > root->right->data)
                root = rightRightRotation(root);
            else
                root = rightLeftRotation(root);
        }
    }
    root->height = max(height(root->left), height(root->right)) + 1;
    return root;
}


int main()
{
    Node* root = new Node;
    root->left = 0;
    root->right = 0;
    root->data = 0;
    int x;
    while (scanf("%d", &x) != EOF)
    {
        if (root->data == 0)
            root->data = x;
        else
            insert(root, x);
        if (cin.get() == '\n')
            break;
    }
    fsearsh(root);
}