// Arup Guha
// 11/14/2023
// Solution to COP 3502 Program 5: Theater Loyalty Program

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

#define MAXLEN 19

typedef struct customer {
    char name[MAXLEN+1];
    int points;
} customer;

typedef struct treenode {
    customer* cPtr;
    int size;
    struct treenode* left;
    struct treenode* right;
} treenode;

// These functions support building the tree.
treenode* insert(treenode* root, customer* cPtr);
int namecmp(customer* c1, customer* c2);
treenode* makenode(customer* cPtr);

// These functions support actions #1, #2, #4 and #5
treenode** search(treenode* root, char* thisname, int flag);
treenode* addpoints(treenode* root, char* thisname, int pts);
void printstatus(customer* cPtr);
int countsmaller(treenode* root, char* thisname);

// All of these functions support the sort at the end.
void preorder(treenode* oak, customer** clist, int* sPtr);
void merge(customer** clist, int low, int mid, int high);
void mergesort(customer** clist, int low, int high);
int ptscmp(customer* c1, customer* c2);

// All of these function support the delete operation.
treenode* delcustomer(treenode* root, char* thisname, int flag);
int isleafnode(treenode* tnode);
int oneleftchild(treenode* tnode);
int onerightchild(treenode* tnode);
void subone(treenode* root, treenode * target);
treenode* max(treenode* root);

// For clean up.
void freetree(treenode* root);
void freenode(treenode* tnode);

int main() {

    // Get # of actions to perform.
    int n;
    scanf("%d", &n);

    // My tree.
    treenode* oak = NULL;

    // Process each action.
    for (int loop=0; loop<n; loop++) {

        // All commands are followed by a name.
        char cmd[MAXLEN+1];
        char name[MAXLEN+1];
        int pts;
        scanf("%s%s", cmd, name);

        // Process add.
        if (strcmp(cmd, "add") == 0) {
            scanf("%d", &pts);
            oak = addpoints(oak, name, pts);
        }

        // Process sub. Just negate pts.
        else if (strcmp(cmd, "sub") == 0) {
            scanf("%d", &pts);
            oak = addpoints(oak, name, -pts);
        }

        // Process del.
        else if (strcmp(cmd, "del") == 0) {
            oak = delcustomer(oak, name, 1);
        }

        // Process search.
        else if (strcmp(cmd, "search") == 0) {

            // Run search.
            treenode** nodes = search(oak, name, 1);

            // Not found case.
            if (nodes[0] == NULL)
                printf("%s not found\n", name);
        }

        // Process count_smaller.
        else {
            printf("%d\n", countsmaller(oak, name));
        }
    }

    // Set up copying nodes into array.
    int size = 0;
    customer** clist = calloc(n, sizeof(customer*));

    // Copy them in via preorder traversal.
    preorder(oak, clist, &size);

    // Trim the fat!
    clist = realloc(clist, size*sizeof(customer*));
    mergesort(clist, 0, size-1);
    for (int i=0; i<size; i++)
        printstatus(clist[i]);

    // Clean up tree...
    freetree(oak);

    // Only thing that needs to be freed from array.
    free(clist);

    return 0;
}

// Inserts a new customer pointed to by cPtr into the tree pointed to by root, returning a
// pointer to the resulting tree.
treenode* insert(treenode* root, customer* cPtr) {

    // Base case.
    if (root == NULL) return makenode(cPtr);

    // This always happens.
    root->size++;

    // Otherwise, recursively insert on the appropriate side.
    if (namecmp(cPtr, root->cPtr) < 0)
        root->left = insert(root->left, cPtr);
    else
        root->right = insert(root->right, cPtr);

    // Return ptr to root.
    return root;
}

// Returns a new leaf node storing the customer pointed to by cPtr.
treenode* makenode(customer* cPtr) {

    // Allocate space.
    treenode* res = malloc(sizeof(treenode));

    // Fill everything accordingly.
    res->cPtr = cPtr;
    res->size = 1;
    res->left = NULL;
    res->right = NULL;

    // Return a ptr to this node.
    return res;
}

// Returns an array of size 2 of type treenode*. res[0] is a pointer to the node
// storing the customer with the name thisname. res[1] is pointer to the parent of
// that node. If the node is the root, then the parent is set to null. If the node
// isn't in the tree, then the parent is set to what "would be" the parent of that
// node if it were immediately added to the tree next.
// If flag is set to 1 then an additional print is executed with the depth of the node.
treenode** search(treenode* root, char* thisname, int flag) {

    // This is where we'll store what we're looking for.
    treenode** res = calloc(2, sizeof(treenode*));

    // Current node and parent.
    res[0] = root;
    res[1] = NULL;
    int curdepth = 0;

    // Keep going till we run out of places to go.
    while (res[0] != NULL) {

        // Store the comparison.
        int cmp = strcmp(thisname, res[0]->cPtr->name);

        // We found it!
        if (cmp == 0) {

            // As Anya would say, this is "goofy ya"...but I lose the depth otherwise...
            if (flag) printf("%s %d %d\n", thisname, res[0]->cPtr->points, curdepth);

            // We can return now.
            return res;
        }

        // This node now becomes the parent.
        res[1] = res[0];

        // This is where we go.
        if (cmp < 0)
            res[0] = res[1]->left;
        else
            res[0] = res[1]->right;

        // Update the current depth.
        curdepth++;
    }

    // If we get here, then we never found the node, but parent might be set.
    return res;
}

// Adds pts points to the customer with the name thisname into the tree rooted at root, returning the new
// root of the tree.
treenode* addpoints(treenode* root, char* thisname, int pts) {

    // Look for a node with this name first.
    treenode** nodes = search(root, thisname, 0);

    // Easier case, node exists!
    if (nodes[0] != NULL) {

        // Update score.
        nodes[0]->cPtr->points += pts;

        // Can't go below 0.
        if (nodes[0]->cPtr->points < 0)
            nodes[0]->cPtr->points = 0;

        // We are required to do this. This is the easiest place to do so.
        printstatus(nodes[0]->cPtr);

        // Root is same.
        return root;
    }

    // Special code for subtracting points.
    if (pts < 0) {
        printf("%s not found\n", thisname);
        return root;
    }

    // Make a new customer node, copy in information.
    customer* cPtr = malloc(sizeof(customer));
    strcpy(cPtr->name, thisname);
    cPtr->points = pts;

    // Same - we have to do this and it's easiest here.
    printstatus(cPtr);

    // Insert this new node and return the corresponding new root.
    treenode* newroot = insert(root, cPtr);
    return newroot;
}

// Prints the status of the customer pointed to by cPtr.
void printstatus(customer* cPtr) {
    printf("%s %d\n", cPtr->name, cPtr->points);
}

// Returns a negative integer if c1 comes before c2 via name comparison,
// 0 if they are equal, or a positive integer if c1 comes after c2.
int namecmp(customer* c1, customer* c2) {
    return strcmp(c1->name, c2->name);
}

// Returns a negative integer if c1 comes before c2 via points comparison
// 0 if they are the same, and a positive integer if c1 comes after c2.
int ptscmp(customer* c1, customer* c2) {

    // First go points, largest to smallest.
    if (c1->points != c2->points)
        return c2->points - c1->points;

    // Break ties via name.
    return namecmp(c1, c2);
}

// Copies all customers in tree pointed to by oak into array pointed to by clist. sPtr
// is a pointer to the integer storing the next open slot in clist.
void preorder(treenode* oak, customer** clist, int* sPtr) {

    // Done.
    if (oak == NULL) return;

    // Copy and move our index.
    clist[*sPtr] = oak->cPtr;
    (*sPtr)++;

    // Now go left and right.
    preorder(oak->left, clist, sPtr);
    preorder(oak->right, clist, sPtr);
}

// Merges the sorted lists clist[low..mid] and clist[mid+1..high]
void merge(customer** clist, int low, int mid, int high) {

    // Set up place to copy pts.
    customer** temp = calloc(high-low+1, sizeof(customer*));

    // Set up indexes.
    int i = low, j = mid+1, k = 0;

    // Loop through...
    while (i<=mid || j<=high) {

        // j wins.
        if (i>mid || (j<=high && ptscmp(clist[j], clist[i]) < 0) )
            temp[k++] = clist[j++];

        // i wins.
        else
            temp[k++] = clist[i++];
    }

    // Copy back.
    for (int z=0; z<high-low+1; z++)
        clist[z+low] = temp[z];
}

// Merge sorts clist[low..high] according to ptscmp.
void mergesort(customer** clist, int low, int high) {

    // Done!
    if (low >= high) return;

    // Recursively sort both sides.
    int mid = (low+high)/2;
    mergesort(clist, low, mid);
    mergesort(clist, mid+1, high);
    merge(clist, low, mid, high);
}

// Returns the number of nodes in the tree rooted at root that have customers
// that come before thisname, alphabetically.
int countsmaller(treenode* root, char* thisname) {

    // Store answer here.
    int res = 0;

    // We can stop when there's no more candidates.
    while (root != NULL) {

        // Compare our name to root's name.
        int cmp = strcmp(root->cPtr->name, thisname);
        int leftsize = root->left == NULL ? 0 : root->left->size;

        // Whole left and root count.
        if (cmp < 0) {
            res += (leftsize + 1);
            root = root->right;
        }

        // root is equal, so we know exact answer.
        else if (cmp == 0)
            return res + leftsize;

        // Everything that is part of our answer is left.
        else
            root = root->left;
    }

    return res;
}

// Frees both the memory for the customer and the treenode pointed to by tnode.
void freenode(treenode* tnode) {
    free(tnode->cPtr);
    free(tnode);
}

// Frees all the dynamically allocated memory directly or indirectly pointed to by root.
void freetree(treenode* root) {
    if (root == NULL) return;
    freetree(root->left);
    freetree(root->right);
    freenode(root);
}

// Returns 1 iff the node pointed to by tnode is a leaf node.
int isleafnode(treenode* tnode) {
    return tnode != NULL && tnode->left == NULL && tnode->right == NULL;
}

// Returns 1 iff the node pointed to by tnode has a left child but not a right.
int oneleftchild(treenode* tnode) {
    return tnode != NULL && tnode->left != NULL && tnode->right == NULL;
}

// Returns 1 iff the node pointed to by tnode has a right child but not a left.
int onerightchild(treenode* tnode) {
    return tnode != NULL && tnode->right != NULL && tnode->left == NULL;
}

// Deletes the node that stores a customer with the name thisname (if it exists), and returns a pointer to
// the resulting tree. If no such customer is in the tree, no action is taken (except for printing this
// information.) If flag is one, information is printed, if it is 0, it is not.
treenode* delcustomer(treenode* root, char* thisname, int flag) {

    // Run the search.
    treenode** nodes = search(root, thisname, 0);

    // Easy case.
    if (nodes[0] == NULL) {
        printf("%s not found\n", thisname);
        return root;
    }

    // Easiest to do this here.
    if (flag) printf("%s deleted\n", thisname);

    // Node is leaf node - yeah!
    if (isleafnode(nodes[0])) {

        // Update the parent node link.
        if (nodes[1] != NULL) {
            if (nodes[1]->left == nodes[0])
                nodes[1]->left = NULL;
            else
                nodes[1]->right = NULL;

            // Updates sizes of subtrees from root to parent of deleted node.
            subone(root, nodes[1]);
        }

        // We can just free this memory.
        freenode(nodes[0]);

        // This is the new root of the tree.
        return nodes[1] != NULL ? root : NULL;
    }

    // One child case - left child
    if (oneleftchild(nodes[0])) {

        // No parent.
        if (nodes[1] == NULL) {
            treenode* retval = nodes[0]->left;
            freenode(nodes[0]);
            return retval;
        }

        // Parent's left and child's left.
        if (nodes[1]->left == nodes[0]) {
            nodes[1]->left = nodes[0]->left;
            freenode(nodes[0]);
        }

        // Parent's right, child's left.
        else {
            nodes[1]->right = nodes[0]->left;
            freenode(nodes[0]);
        }

        // Update sizes, return root.
        subone(root, nodes[1]);
        return root;
    }

    // One child case - right child
    else if (onerightchild(nodes[0])) {

        // No parent.
        if (nodes[1] == NULL) {
            treenode* retval = nodes[0]->right;
            freenode(nodes[0]);
            return retval;
        }

        // Parent's left and child's right.
        if (nodes[1]->left == nodes[0]) {
            nodes[1]->left = nodes[0]->right;
            freenode(nodes[0]);
        }

        // Parent's right, child's left.
        else {
            nodes[1]->right = nodes[0]->right;
            freenode(nodes[0]);
        }

        // This hasn't changed.
        subone(root, nodes[1]);
        return root;
    }

    // Ugh! Two child case.
    else {

        // Returns node to be physically deleted.
        treenode* realdel = max(nodes[0]->left);

        // Temporarily store this stuff.
        char cpname[MAXLEN+1];
        strcpy(cpname, realdel->cPtr->name);
        int cppts = realdel->cPtr->points;

        // Delete the physical node we want to delete. This will change sizes.
        treenode* retval = delcustomer(root, cpname, 0);

        // Restore this information.
        strcpy(nodes[0]->cPtr->name, cpname);
        nodes[0]->cPtr->points = cppts;

        // Finally!
        return retval;
    }

}

// Returns the node with the maximum item in the tree rooted at root.
treenode* max(treenode* root) {
    if (root == NULL) return NULL;
    if (root->right == NULL) return root;
    return max(root->right);
}

// Subtracts 1 from each subtree size starting at root going down to target.
void subone(treenode* root, treenode * target) {

    // Go down tree.
    while (root != NULL) {

        // Update size.
        root->size--;

        // We got to where we're aiming to go, get out.
        if (root == target) break;

        // If not equal, go the appropriate direction.
        if (namecmp(target->cPtr, root->cPtr) < 0)
            root = root->left;
        else
            root = root->right;
    }
}