// Arup Guha
// 11/13/2025
// Solution to COP 3502 Program #5: Games Dictionary

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

#define MAXSIZE 19
#define NUMGAMES 6
#define MAXNODES 200000

typedef struct NYT_String {
    char* str;
    int allowed[NUMGAMES];
} NYT_String;

typedef struct BST_Node {
    NYT_String* ptr;
    struct BST_Node* left;
    struct BST_Node* right;
} BST_Node;

// Functions to create the "objects" for the program.
BST_Node* makeNode(char* word, int gID);
NYT_String* makeString(char* word, int gID);

// Functions for Option 1: Add an item.
BST_Node* addEntry(BST_Node* root, char* word, int gID);
BST_Node* insert(BST_Node* root, BST_Node* newNode);

// Functions for Option 2: Delete an item.
BST_Node* deleteEntry(BST_Node* root, char* word, int gID);
BST_Node* removeNode(BST_Node* root, BST_Node* delNode);
BST_Node* maxPtr(BST_Node* root);
BST_Node* getParent(BST_Node* root, BST_Node* delNode);
NYT_String* copy(NYT_String* ptr);
int numGames(const NYT_String* ptr);

// For option 3.
BST_Node* search(BST_Node* root, char* word);
void printList(NYT_String* sPtr);

// Functions for option 4.
char** allStringsInGame(BST_Node* root, int gameNo, int* arrSize);
int allStringsInGameRec(BST_Node* root, char** wordList, int gameNo, int seen);
void printWords(char** wordList, int numWords);
void freeList(char** wordList, int numWords);

// For option 5.
int numStringsInGame(BST_Node* root, int gameID, int length);

// For option 6.
void updateNext(BST_Node* root, char* target, char* cur);

// For clean up.
void freeNode(BST_Node* node);
void freeTree(BST_Node* root);

int main() {

    // My dictionary.
    BST_Node* allWords = NULL;

    // Get # of operations.
    int numOps, op;
    scanf("%d", &numOps);

    // Go through each operation.
    for (int loop=0; loop<numOps; loop++) {

        // Get operation.
        scanf("%d", &op);

        // Seems like a better place for this.
        char word[MAXSIZE+1];
        int gID, len;

        // Get game and word, add to tree!
        if (op == 1) {
            scanf("%d%s", &gID, word);
            allWords = addEntry(allWords, word, gID);
        }

        // Delete.
        else if (op == 2) {
            scanf("%d%s", &gID, word);
            allWords = deleteEntry(allWords, word, gID);
        }

        // Search.
        else if (op == 3) {

            // Get word for search.
            scanf("%s", word);

            // Find the node.
            BST_Node* tmp = search(allWords, word);

            // It doesn't exist.
            if (tmp == NULL)
                printf("-1\n");

            // Print out the list of games for this word.
            else
                printList(tmp->ptr);
        }

        // Process getting all strings in a game.
        else if (op == 4) {

            // Get game for search.
            scanf("%d", &gID);

            // Get the results.
            int numAns = 0;
            char** res = allStringsInGame(allWords, gID, &numAns);

            // Print them.
            printWords(res, numAns);

            // Free this memory.
            freeList(res, numAns);
        }

        // Read and process query.
        else if (op == 5) {
            scanf("%d%d", &gID, &len);
            printf("%d\n", numStringsInGame(allWords, gID, len));
        }

        // Choice 6.
        else {

            // Get the word.
            scanf("%s", word);

            // I need this to be the empty string to work.
            char res[MAXSIZE+1];
            res[0]='\0';

            // Run it and print.
            updateNext(allWords, word, res);

            // We got one.
            if (strcmp(res, ""))
                printf("%s\n", res);

            // This is what we're supposed to output.
            else
                printf("NO SUCCESSOR\n");
        }
    }

    /** Free rest ***/
    freeTree(allWords);

    return 0;
}

// Returns a new node with the word word allowed for the game with ID gID.
BST_Node* makeNode(char* word, int gID) {

    // Make the node.
    BST_Node* res = malloc(sizeof(BST_Node));
    res->left = NULL;
    res->right = NULL;

    // Make the string and return.
    res->ptr = makeString(word, gID);
    return res;
}

// Returns a pointer to a newly created NYT_String struct storing word which is allowed only
// in the game gID.
NYT_String* makeString(char* word, int gID) {

    // Copy the string.
    NYT_String* res = malloc(sizeof(NYT_String));
    int len = strlen(word);
    res->str = calloc(len+1, sizeof(char));
    strcpy(res->str, word);

    // Set the allowed games.
    for (int i=0; i<NUMGAMES; i++)
        res->allowed[i] = 0;
    res->allowed[gID] = 1;

    // Here is the node to return.
    return res;
}

// Adds an entry into the tree pointed to by root with an entry allowing word in the game with ID gID.
BST_Node* addEntry(BST_Node* root, char* word, int gID) {

    // See if this word is allowed in some game.
    BST_Node* item = search(root, word);

    // Word not in tree yet, so we need to add a physical node.
    if (item == NULL) {

        // Make the new node.
        BST_Node* newNode = makeNode(word, gID);

        // Insert this node into the tree with root and return the resulting root.
        return insert(root, newNode);
    }

    // This is easy!
    item->ptr->allowed[gID] = 1;
    return root;
}

// Returns a pointer to the node in the tree rooted at root storing word. Returns NULL
// if no such node exists.
BST_Node* search(BST_Node* root, char* word) {

    // Not here.
    if (root == NULL) return NULL;

    // Compare word to the word stored in root.
    int cmp = strcmp(word, root->ptr->str);

    // Gotta look left.
    if (cmp < 0)
        return search(root->left, word);

    // Here we go right.
    else if (cmp > 0)
        return search(root->right, word);

    // We got it!
    else
        return root;
}


// Pre-condition: No node storing the word in newNode (a ptr to a single node) is already stored in
// the tree pointed to by root.
// Post-condition: newNode is inserted into the tree with the root root and a pointer to the new root of
// the tree is returned.
BST_Node* insert(BST_Node* root, BST_Node* newNode) {

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

    // Need to go left.
    if (strcmp(newNode->ptr->str, root->ptr->str) < 0)
        root->left = insert(root->left, newNode);

    // Need to go right if we get here.
    else
        root->right = insert(root->right, newNode);

    // This is our root.
    return root;
}

// Returns the number of strings in the tree rooted at root in the game with
// the id gameID with the length, length.
int numStringsInGame(BST_Node* root, int gameID, int length) {

    // None.
    if (root == NULL) return 0;

    // Number of valid words at the root (if this is all true we count it, otherwise we don't.
    int res = (strlen(root->ptr->str) == length) && root->ptr->allowed[gameID];

    // Now add in left and right and return.
    res += numStringsInGame(root->left, gameID, length);
    res += numStringsInGame(root->right, gameID, length);
    return res;
}

// Returns a list of all the strings stored in the tree rooted at root in the game gameNo and
// stores the number of strings in the int variable pointed to by arrSize.
char** allStringsInGame(BST_Node* root, int gameNo, int* arrSize) {
    char** res = calloc(MAXNODES, sizeof(char*));
    *arrSize = allStringsInGameRec(root, res, gameNo, 0);
    res = realloc(res, sizeof(char*)*(*arrSize));
    return res;
}

// Returns the number of strings in the tree pointed to by root in game gameNo AND
// stores them in wordList, given that seen number of strings have already been stored
// in wordList.
int allStringsInGameRec(BST_Node* root, char** wordList, int gameNo, int seen) {

    // Easy case.
    if (root == 0) return 0;

    // Recursively go left for alpha order.
    int onLeft = allStringsInGameRec(root->left, wordList, gameNo, seen);

    // See if this word at the root works.
    int inRoot = root->ptr->allowed[gameNo];

    // This is a word to copy into the word list. It goes in index onLeft.
    if (inRoot) {
        int len = strlen(root->ptr->str);

        // So seen is how many had previously been assigned before getting into this function call
        // and onLeft was how many were pass on the left before getting to the root.
        wordList[seen+onLeft] = calloc(len+1, sizeof(char));
        strcpy(wordList[seen+onLeft], root->ptr->str);
    }

    // This is how many are on the right.
    int onRight = allStringsInGameRec(root->right, wordList, gameNo, seen+onLeft+inRoot);

    // Total in this subtree.
    return onLeft + inRoot + onRight;
}

// Prints the first numWords words stored in wordList.
void printWords(char** wordList, int numWords) {
    for (int i=0; i<numWords; i++)
        printf("%s\n", wordList[i]);
}

// Frees all memory pointed to by wordList, which points to numWords strings.
void freeList(char** wordList, int numWords) {
    for (int i=0; i<numWords; i++)
        free(wordList[i]);
    free(wordList);
}

// Prints the list of games that the string pointed to by sPtr is allowed in.
void printList(NYT_String* sPtr) {
    for (int i=0; i<NUMGAMES; i++)
        if (sPtr->allowed[i])
            printf("%d ", i);
    printf("\n");
}

// Copies the correct next string (after target) into cur of all strings in the tree rooted at root.
void updateNext(BST_Node* root, char* target, char* cur) {

    // How we deal with the base case.
    if (root == NULL) return;

    // Answer can't be anything later than the root string.
    if (strcmp(target, root->ptr->str) < 0) {

        // A new current string so copy it.
        if (!strcmp(cur,"") || (strcmp(root->ptr->str,cur) < 0))
            strcpy(cur, root->ptr->str);

        updateNext(root->left, target, cur);
    }

    // Nothing on left is valid. So no updates and just go right.
    else {
        updateNext(root->right, target, cur);
    }
}

// Deletes the entry for word in the game with id gID in the tree rooted at root.
BST_Node* deleteEntry(BST_Node* root, char* word, int gID) {

    // See if this word is allowed in some game.
    BST_Node* item = search(root, word);

    // Easy case. No node deletion, just subtract 1 from the value.
    if (numGames(item->ptr) > 1) {
        item->ptr->allowed[gID] = 0;
        return root;
    }

    // Here we do a physical node removal.
    return removeNode(root, item);
}

// Returns the number of games that the NYT_String pointed to by ptr is allowed in.
int numGames(const NYT_String* ptr) {
    int res = 0;
    for (int i=0; i<NUMGAMES; i++)
        res += ptr->allowed[i];
    return res;
}

// Removes the physical node delNode from the tree rooted at root. delNode is guaranteed to be in the
// tree rooted at root.
BST_Node* removeNode(BST_Node* root, BST_Node* delNode) {

    // Two child case.
    if (delNode->left != NULL && delNode->right != NULL) {

        // I am going with the max on the left to replace delNode.
        BST_Node* maxLeft = maxPtr(delNode->left);
        NYT_String* tmp = copy(maxLeft->ptr);

        // Now, just remove the maxLeft node, which can't have two children.
        root = removeNode(root, maxLeft);

        // Free the data that no longer needs to be there,
        free(delNode->ptr->str);
        free(delNode->ptr);

        // This is what it should point to instead.
        delNode->ptr = tmp;

        // This is the root to return in this case.
        return root;
    }

    // If we get here, we're deleting the root and it has at most one child.
    if (root == delNode) {

        // This will be the new root. Works when root is only node and when it's not.
        BST_Node* newRoot = root->left == NULL ? root->right : root->left;

        // Free it and return the new root.
        freeNode(root);
        return newRoot;
    }

    // Get the parent of delNode in the tree rooted at root.
    BST_Node* par = getParent(root, delNode);

    if (delNode->left == NULL && delNode->right == NULL) {
        if (par->left == delNode) {
            freeNode(delNode);
            par->left = NULL;
        }
        else {
            freeNode(delNode);
            par->right = NULL;
        }
        return root;
    }

    // Set up a pointer to the parent link we'll need to change.
    BST_Node** parLink = par->left == delNode ? &(par->left) : &(par->right);

    // And a link to the child we'll have to link it to.
    BST_Node* connect = delNode->left == NULL ? delNode->right : delNode->left;

    // Free it!
    freeNode(delNode);

    // This takes are of all 4 cases!!!
    *parLink = connect;

    return root;
}

// Pre-condition: delNode is in the tree rooted at root and is NOT equal to root.
// Post-condition: returns the parent of delNode in the tree rooted at root.
BST_Node* getParent(BST_Node* root, BST_Node* delNode) {

    // We found it!
    if (root->left == delNode || root->right == delNode) return root;

    // Compare root with delNode to see what direction we have to go.
    int cmp = strcmp(delNode->ptr->str, root->ptr->str);

    // Go left or right, accordingly.
    return cmp > 0 ? getParent(root->right, delNode) : getParent(root->left, delNode);
}

// Returns a pointer to the max node stored in the tree rooted at root.
BST_Node* maxPtr(BST_Node* root) {

    // I don't normally write this stuff iteratively, but this works...
    while (root->right != NULL)
        root = root->right;

    // This is the node storing the largest value in the desired tree.
    return root;
}

// Dynamically allocates memory for a new NYT_String and copies the contents pointed to by ptr into it
// and returns the pointer to this new memory.
NYT_String* copy(NYT_String* ptr) {
    NYT_String* res = malloc(sizeof(NYT_String));
    res->str = calloc(strlen(ptr->str)+1, sizeof(char));
    strcpy(res->str, ptr->str);
    for (int i=0; i<NUMGAMES; i++)
        res->allowed[i] = ptr->allowed[i];
    return res;
}

// Frees all memory associated with the single node pointed to by node.
void freeNode(BST_Node* node) {
    free(node->ptr->str);
    free(node->ptr);
    free(node);
}

// Frees all memory associated with the tree pointed to by root.
void freeTree(BST_Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    freeNode(root);
}