#include <iostream>
#include <string>

using namespace std;



struct Node {
    int bf;
    Node * up;
    Node * left;
    Node * right;
    string value;
    string lines = "";
};

class AVLTree {
private:
    Node * root;
public:
    AVLTree();
    ~AVLTree();
    void add(string, int);
    void r_rotate(Node *);
    void l_rotate(Node *);
    void rl_rotate(Node *);
    void lr_rotate(Node *);
    void show_inorder(Node *);
    Node * find(string);
};

AVLTree::AVLTree() {
    this->root = NULL;
}

AVLTree::~AVLTree() {
    //...
}
void AVLTree::add(string value, int line) {
    if (root == NULL) {
        root = new Node;
        root->value = value;
        root->lines += to_string(line);
        root->up = NULL;
        root->left = NULL;
        root->right = NULL;
        root->bf = 0;
    }
    else {
        Node * tmp = find(value);
        if (tmp != NULL) {
            tmp->lines = tmp->lines + " " + to_string(line);
        }
        else {
            Node * new_node = new Node;
            new_node->left = NULL;
            new_node->right = NULL;
            new_node->value = value;
            new_node->lines += to_string(line);
            new_node->bf = 0;
            Node * tmp = root;
            bool running = false;
            while (running) {
                if (value < tmp->value) {
                    if (tmp->left == NULL) {
                        tmp->left = new_node;
                        running = false;
                    }
                    else {
                        tmp = tmp->left;
                    }
                }
                else {
                    if (tmp->right == NULL) {
                        tmp->right = new_node;
                        running = false;
                    }
                    else {
                        tmp = tmp->right;
                    }
                }
            }
            new_node->up = tmp;
            if (tmp->bf == 0) {
                if (tmp->left == new_node) {
                    tmp->bf = 1;
                }
                else {
                    tmp->bf = -1;
                }
            }
            else {
                tmp->bf = 0;
            }
            Node * tmp_parent = new Node;
            tmp_parent = tmp->up;
            while (tmp_parent != NULL) {
                if (tmp_parent->bf != 0) {
                    if (tmp_parent->bf == -1) {
                        if (tmp_parent->left == tmp) {
                            tmp_parent->bf = 0;
                        }
                        else {
                            if (tmp->bf == 1) {
                                rl_rotate(tmp_parent);
                            }
                            else {
                                r_rotate(tmp_parent);
                            }
                        }
                    }
                    else {
                        if (tmp_parent->right == tmp) {
                            tmp_parent->bf = 0;
                        }
                        else {
                            if (tmp->bf == -1) {
                                lr_rotate(tmp_parent);
                            }
                            else {
                                l_rotate(tmp_parent);
                            }
                        }
                    }
                }
                else {
                    if (tmp_parent->left == tmp) {
                        tmp_parent->bf = 1;
                    }
                    else {
                        tmp_parent->bf = -1;
                    }
                    tmp = tmp_parent;
                }
            }
        }
    }
}
void AVLTree::r_rotate(Node * tmp_parent) {
    //...
}

void AVLTree::l_rotate(Node * tmp_parent) {
    //...
}

void AVLTree::rl_rotate(Node * tmp_parent) {
    //...
}

void AVLTree::lr_rotate(Node * tmp_parent) {
    //...
}

Node * AVLTree::find(string value) {
    //...
    return NULL;
}
void AVLTree::show_inorder(Node * root) {
    if (root != NULL) {
        show_inorder(root->left);
        cout << root->value << " => " << root->lines << endl;
        show_inorder(root->right);
    }
}


int main() {
    int n, i = 1;
    string * array;
    cin >> n;
    array = new string[n];
    while (n <= i) {
        getline(cin, array[i]);
    }
    delete[] array;
    system("pause");
    return 0;
}