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

enum {RED, BLACK};

struct TreeNode {
    int data;
    int color;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
};

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->color );
    structure ( root->left, level + 1 );
  }
}

struct TreeNode *createNode(int value) {
    struct TreeNode *node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if(!node) {
        printf("Memory error\n");
        exit(1);
    }

    node -> data = value;
    node -> color = RED;    // novi cvor je crven
    node -> left = node -> right = node -> parent = NULL;

    return node;
}

void leftRotate(struct TreeNode **root) {
    struct TreeNode *x, *y;

    x = *root;
    y = x -> right;

    x -> right = y -> left;
    if(y -> left) y -> left -> parent = x;

    y -> parent = x -> parent;
    if(x -> parent) {
        if (x == x -> parent -> left) x -> parent -> left = y;
        else x -> parent -> right = y;
    }

    y -> left = x;
    x -> parent = y;
    *root = y;
}

void rightRotate(struct TreeNode **root) {
    struct TreeNode *x, *y;

    y = *root;
    x = y -> left;

    y -> left = x -> right;
    if (x -> right) x -> right -> parent = y;

    x -> parent = y -> parent;
    if (y -> parent) {
        if (y == y -> parent -> left) y -> parent -> left = x;
        else y -> parent -> right = x;
    }

    x -> right = y;
    y -> parent = x;
    *root = x;
}

void fixColors(struct TreeNode **root, struct TreeNode *node) {
    struct TreeNode *uncle, *grandparent;

    while(node -> parent && node -> parent -> color == RED) {
        if (node -> parent == node -> parent -> parent -> left) { // nas roditelj (node) je levo dete svom roditelju
            uncle = node -> parent -> parent -> right;
            if (uncle && uncle -> color == RED) {   // imamo ujaka i njegova boja je crvena
                node -> parent -> color = BLACK;
                uncle -> color = BLACK;
                node -> parent -> parent -> color = RED;
                node = node -> parent -> parent;
            }
            else {                                  // nemamo ujaka ili je on crne boje
                if(node == node -> parent -> right) {
                    node = node -> parent;
                    leftRotate(&node);
                    if(node -> parent == NULL) *root = node;
                    node = node -> left;
                }
                node -> parent -> color = BLACK;
                node -> parent -> parent -> color = RED;
                grandparent = node -> parent -> parent;
                rightRotate(&grandparent);
                if(grandparent -> parent == NULL) *root = grandparent;
            }
        }
        else { // nas roditelj (node) je desno dete svom roditelju
            uncle = node -> parent -> parent -> left;
            if (uncle && uncle -> color == RED) {
                node -> parent -> color = BLACK;
                uncle -> color = BLACK;
                node -> parent -> parent -> color = RED;
                node = node -> parent -> parent;
            }
            else {                                          // nemamo ujaka ili je on crne boje
                if (node == node -> parent -> left) {
                    node = node -> parent;
                    rightRotate(&node);
                    if(node -> parent == NULL) *root = node;
                    node = node -> right;
                }
                node -> parent -> color = BLACK;
                node -> parent -> parent -> color = RED;
                grandparent = node -> parent -> parent;
                leftRotate(&grandparent);
                if(grandparent -> parent == NULL) *root = grandparent;
            }
        }
    }

    (*root) -> color = BLACK;
}

void insertNode(struct TreeNode **root, int value) {
    struct TreeNode *node = createNode(value);
    struct TreeNode *current, *parent;

    current = *root;
    parent = NULL;
    while(current) {
        parent = current;
        if (value < current -> data) current = current -> left;
        else current = current -> right;
    }

    node -> parent = parent;
    if(parent == NULL) *root = node;
    else if(value < parent -> data) parent -> left = node;
    else parent -> right = node;

    fixColors(root, node);
}

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

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

    return root;
}

int main() {

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

    return 0;
}