// Arup Guha
// 11/14/2021
// Solution to COP 3502 Program #5: Word Sort

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

#define MAX 20

typedef struct word {
    char item[MAX+1];
    int freq;
} word;

typedef struct node {
    word* wordPtr;
    int depth;
    struct node* left;
    struct node* right;
} node;

// Functions for the tree.
node* insert(node* root, char* myword, int curD);
int* makeQuery(node* root, char* myword);
int* makeArray(int a, int b);
void freeTree(node* root);

// Functions to dynamically create structs.
node* makeNewTreeNode(char* myword, int curD);
word* makeNewItem(char* myword);

// Functions for phase 2 of the assignment.
int numTreeNodes(node* root);
void copyToArray(word** array, node* root);
void mergeSort(word** array, int low, int high);
void merge(word** array, int s1, int s2, int e2);
int compare(word* w1, word* w2);

// Global variable to make copying items into array easy.
int arrayIdx;

int main(void) {

    // Read in number of commands.
    int numC;
    scanf("%d", &numC);

    // Initial tree.
    node* tree = NULL;

    // Process commands.
    for (int loop=0; loop<numC; loop++) {

        // Read in the command.
        int type;
        char myword[MAX+1];
        scanf("%d%s", &type, myword);

        // Insert.
        if (type == 1)
            tree = insert(tree, myword, 0);

        // Query.
        else {
            int* res = makeQuery(tree, myword);
            printf("%d %d\n", res[0], res[1]);
            free(res);
        }
    }

    // Get the number of tree nodes.
    int numNodes = numTreeNodes(tree);

    // Make room for array pointers to the item nodes.
    word** array = malloc(sizeof(word*)*numNodes);

    // Set this so our copying goes to the right indexes.
    arrayIdx = 0;

    // Copy the links to the nodes from the tree to the array.
    copyToArray(array, tree);

    // Sort it.
    mergeSort(array, 0, numNodes-1);

    // Print it.
    for (int i=0; i<numNodes; i++)
        printf("%s %d\n", array[i]->item, array[i]->freq);

    // Only frees memory for pointers stored in array.
    free(array);

    // This frees all of the tree memory.
    freeTree(tree);

    return 0;
}

// Inserts word into the tree pointed to by root.
node* insert(node* root, char* myword, int curD) {

    // Base case - new word since the tree is empty.
    if (root == NULL)
        return makeNewTreeNode(myword, curD);

    // Safe to compare my word to the root's word.
    int cmp = strcmp(myword, root->wordPtr->item);

    // Go left.
    if (cmp < 0)
        root->left = insert(root->left, myword, curD+1);

    // Go right.
    else if (cmp > 0)
        root->right = insert(root->right, myword, curD+1);

    // Add 1 to frequency.
    else
        root->wordPtr->freq++;

    // Have to return the root of the tree.
    return root;
}

// Returns the depth of the word in the tree rooted at root (based on what's stored in its node.)
int* makeQuery(node* root, char* myword) {

    // Word not found, return -1.
    if (root == NULL)
        return makeArray(-1,-1);

    // Safe to compare my word to the root's word.
    int cmp = strcmp(myword, root->wordPtr->item);

    // Go left.
    if (cmp < 0)
        return makeQuery(root->left, myword);

    // Go right.
    else if (cmp > 0)
        return makeQuery(root->right, myword);

    // We found the node, so return its depth.
    else
        return makeArray(root->wordPtr->freq, root->depth);
}

// Dynamically allocates an array of size 2, stores a and b in it and returns a pointer to the array.
int* makeArray(int a, int b) {
    int* tmp = malloc(sizeof(int)*2);
    tmp[0] = a;
    tmp[1] = b;
    return tmp;
}

// Returns a new tree node for myword at depth curD.
node* makeNewTreeNode(char* myword, int curD) {
    node* tmp = malloc(sizeof(node));
    tmp->wordPtr = makeNewItem(myword);
    tmp->depth = curD;
    tmp->left = NULL;
    tmp->right = NULL;
    return tmp;
}

// Creates a new node with myword of frequency 1 and returns a pointer to it.
word* makeNewItem(char* myword) {
    word* tmp = malloc(sizeof(word));
    strcpy(tmp->item, myword);
    tmp->freq = 1;
    return tmp;
}

// Returns the number of unique tree nodes in the tree rooted at root.
int numTreeNodes(node* root) {

    // No nodes.
    if (root == NULL) return 0;

    // Recursive breakdown.
    return 1 + numTreeNodes(root->left) + numTreeNodes(root->right);
}

// Copies all of the word pointers in the tree rooted at root into array.
void copyToArray(word** array, node* root) {

    // No work to be done.
    if (root == NULL) return;

    // Copy in the node at the root first
    array[arrayIdx++] = root->wordPtr;

    // Recursively copy left subtree, then right subtree.
    copyToArray(array, root->left);
    copyToArray(array, root->right);
}

// Frees all the dynamically associated memory in the tree pointed to by root.
void freeTree(node* root) {

    if (root == NULL) return;

    // Recursively free the trees left and right.
    freeTree(root->left);
    freeTree(root->right);

    // First we must free the memory for the word.
    free(root->wordPtr);

    // Then the node itself.
    free(root);
}

// Merge sorts array[low..high] according to the assignment specifications.
void mergeSort(word** array, int low, int high) {

    if (low >= high) return;

    // Sort left half.
    int mid = (low+high)/2;
    mergeSort(array, low, mid);

    // Sort right half.
    mergeSort(array, mid+1, high);

    // Merge together.
    merge(array, low, mid+1, high);
}

// Merges the arrays array[s1..s2-1] and array[s2..e2] into one sorted array in array[s1..e2].
void merge(word** array, int s1, int s2, int e2) {

    // Temporary space to copy pointers.
    word** tmp = malloc(sizeof(word*)*(e2-s1+1));

    // Set up indexes into left and right halves.
    int leftIdx = s1, rightIdx = s2;

    // i is index into copied array.
    for (int i=0; i<e2-s1+1; i++) {

        // Either right index is done, or if left isn't and it's better than right, copy it.
        if (rightIdx > e2 || (leftIdx<s2 && compare(array[leftIdx], array[rightIdx]) < 0))
            tmp[i] = array[leftIdx++];

        // Right index is better.
        else
            tmp[i] = array[rightIdx++];
    }

    // Copy all the links back.
    for (int i=0; i<e2-s1+1; i++)
        array[i+s1] = tmp[i];
}

// Returns a negative integer if the word pointed to by w1 comes before the word pointed to by w2, 0 if
// they are equal and a positive integer otherwise. A word comes before another word if it has a higher
// frequency, or if the two words have the same frequency and the first word comes first alphabetically.
int compare(word* w1, word* w2) {

    // Here is how you sort by frequency, most to least.
    if (w1->freq != w2->freq) return w2->freq - w1->freq;

    // This is regular alpha order.
    return strcmp(w1->item, w2->item);
}