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

struct TreeNode {
    int data;
    int balance;
    struct TreeNode *left;
    struct TreeNode *right;
};

void padding ( char ch, int n )
{
  int i;
  for ( i = 0; i < n; i++ )
    putchar ( ch );
}

void structure ( struct TreeNode *root, int level )
{
  int i;
  if ( root == NULL ) {
    padding ( '\t', level );
    puts ( "~" );
  }
  else {
    structure ( root->right, level + 1 );
    padding ( '\t', level );
    printf ( "%d (%d)\n", root->data, root -> balance );
    structure ( root->left, level + 1 );
  }
}

struct TreeNode* createNewNode(int value) {
    struct TreeNode *node = (struct TreeNode*) malloc(sizeof(struct TreeNode));

    if(!node) {
        printf("Error allocating memory\n");
        exit(1);
    }

    node -> data = value;
    node -> balance = 0;
    node -> left = node -> right = NULL;

    return node;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int treeDepth(struct TreeNode *root) {
    if(!root) return 0;

    int leftDepth = treeDepth(root -> left);
    int rightDepth = treeDepth(root -> right);

    return 1 + max(leftDepth, rightDepth);
}

void leftRotate(struct TreeNode **node) {
    struct TreeNode *pomLeft = *node;
    struct TreeNode *pomRight = pomLeft -> right;

    pomLeft -> right = pomRight -> left;
    pomRight -> left = pomLeft;
    *node = pomRight;

    pomLeft -> balance = treeDepth(pomLeft -> right) - treeDepth(pomLeft -> left);
    pomRight -> balance = treeDepth(pomRight -> right) - treeDepth(pomRight -> left);
}

void rightRotate(struct TreeNode **node) {
    struct TreeNode *pomLeft, *pomRight;

    pomRight = *node;
    pomLeft = pomRight -> left;
    pomRight -> left = pomLeft -> right;
    pomLeft -> right = pomRight;
    *node = pomLeft;

    pomRight -> balance = treeDepth(pomRight -> right) - treeDepth(pomRight -> left);
    pomLeft -> balance = treeDepth(pomLeft -> right) - treeDepth(pomLeft -> left);
}

int addNode(struct TreeNode **root, int value) {
    if(*root == NULL) {
        *root = createNewNode(value);
        return 1;
    }

    struct TreeNode *pomNode = *root;
    int increment, result = 0;

    if (value < pomNode -> data) increment = -addNode(&(pomNode->left), value);
    else increment = addNode(&(pomNode->right), value);

    pomNode -> balance += increment;

    if (increment != 0 && pomNode -> balance != 0) {
        if (pomNode -> balance < -1) {
            if (pomNode -> left -> balance < 0) rightRotate(&pomNode);
            else {
                leftRotate(&(pomNode -> left));
                rightRotate(&pomNode);
            }
        }
        else if (pomNode -> balance > 1) {
            if (pomNode -> right -> balance > 0) leftRotate(&pomNode);
            else {
                rightRotate(&(pomNode -> right));
                leftRotate(&pomNode);
            }
        }
        else {
            result = 1;
        }
    }
    *root = pomNode;

    return result;
}

struct TreeNode* formTree() {
    struct TreeNode *root = NULL;
    int value;

    scanf("%d", &value);
    while(value) {
        addNode(&root, value);
        structure(root, 0);
        printf("----------------------------\n");
        scanf("%d", &value);
    }

    return root;
}

int main() {

    struct TreeNode *root = formTree();
    structure(root, 0);

    return 0;
}