/*******************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : LT-2-ODD-A
* Description : Direct Mapping of Functions
*******************************************/

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

#define MAX_NAME 100
#define MAX_STRING 100000

// structure to keep function name and all map descriptions
typedef struct func {
    char nameFunc[MAX_NAME];
    struct map *arrMap;
    int numMap;
} function;

// structure to keep 'character->string' maps of a function
typedef struct map {
    char lhs;
    char rhs[MAX_STRING];
    int len;
} mapFunc;

// structure to keep example composite function details and input string
typedef struct example {
    struct comp_func *arrCompMap;
    int numComp;
    char inputStr[MAX_STRING];
} mapExample;

// structure to keep each function and its number of applications within each composite function set
typedef struct comp_func {
    char nameExampleFunc[MAX_NAME];
    int numApply;
} compositeFunc;

// function to return the array position (index) of the searched function if found, otherwise return -1
int findFuncIndex(function *fn, int n, char *name)
{
    int i, idx = -1;
    for (i=0; i<n; i++) {
        if (!strcmp(fn[i].nameFunc,name)) {
            idx = i;
            break;
        }
    }
    return idx;
}

// function to return the string corresponding to a character map for a function if found, otherwise return NULL
char *fetchMap(mapFunc *af, int n, char c)
{
    int i;
    char *str = NULL;
    for (i=0; i<n; i++) {
        if(af[i].lhs == c) {
            str = (char *)malloc((strlen(af[i].rhs)+1)*sizeof(char));
            strcpy(str, af[i].rhs);
            break;
        }
    }
    return str;
}

int main()
{
    char tempStr[MAX_STRING];
    char *resultStr, *mapStr;
    int numFunc, numExample, i, j, k, l, resultStrLen, funcIndex;
    function *arrFunc;
    mapExample *arrExample;

    // scanning user inputs: number of defined functions and map information for each function
    scanf("%d", &numFunc);
    arrFunc = (function *)malloc(numFunc * sizeof(function));
    for (i=0; i<numFunc; i++) {
        scanf("%s", arrFunc[i].nameFunc);
        scanf("%d", &(arrFunc[i].numMap));
        arrFunc[i].arrMap = (mapFunc *)malloc((arrFunc[i].numMap) * sizeof(mapFunc));
        for (j=0; j<(arrFunc[i].numMap); j++) {
            scanf(" %c->%s", &(arrFunc[i].arrMap[j].lhs), arrFunc[i].arrMap[j].rhs);
        }
    }
    // scanning user inputs: number of example composite functions and their details + input string for applying the example function
    scanf("%d", &numExample);
    arrExample = (mapExample *)malloc(numExample * sizeof(mapExample));
    for (i=0; i<numExample; i++) {
        scanf("%d", &(arrExample[i].numComp));
        arrExample[i].arrCompMap = (compositeFunc *)malloc((arrExample[i].numComp)*sizeof(compositeFunc));
        for (j=0; j<(arrExample[i].numComp); j++) {
            scanf("%s", arrExample[i].arrCompMap[j].nameExampleFunc);
            scanf("%d", &(arrExample[i].arrCompMap[j].numApply));
        }
        scanf("%s", arrExample[i].inputStr);
    }
    
    // computing functions over input string data and producing results as the output
    printf("\n++ Applied Homomorphism Results ++\n");
    for (i=0; i<numExample; i++) {
        for (l=0; l<(arrExample[i].numComp); l++) {
            printf("%s^%d ", arrExample[i].arrCompMap[l].nameExampleFunc, arrExample[i].arrCompMap[l].numApply);
        }
        printf("(%s) = ", arrExample[i].inputStr);
        resultStr = (char *)malloc((strlen(arrExample[i].inputStr)+1)*sizeof(char));
        strcpy(resultStr, arrExample[i].inputStr);
        for (l=(arrExample[i].numComp)-1; l>=0; l--) { // applying composite function inside-out
            funcIndex = findFuncIndex(arrFunc, numFunc, arrExample[i].arrCompMap[l].nameExampleFunc);
            if (funcIndex == -1) break;
            else {
                for (j=0; j<arrExample[i].arrCompMap[l].numApply; j++) { // applying each function multiple-times as mentioned
                    resultStrLen = strlen(resultStr);
                    for (k=0,tempStr[0]='\0'; k<resultStrLen; k++) { // iterating over each character and mapping it
                        mapStr = fetchMap(arrFunc[funcIndex].arrMap, arrFunc[funcIndex].numMap, resultStr[k]);
                        if (mapStr == NULL) break;
                        strcat(tempStr, mapStr);
                    }
                    if (mapStr == NULL) break;
                    strcpy(resultStr, tempStr);
                }
            }
            if (mapStr == NULL) break;
        }
        if (funcIndex == -1) // function name does not matched with the existing function definitions
            printf("Function '%s' Does Not Exist! (ERROR)\n", arrExample[i].arrCompMap[l].nameExampleFunc);
        else if (mapStr == NULL) // character map is not defined for the given function
            printf("Homomorphism for '%c' in Function '%s' is Undefined! (ERROR)\n", resultStr[k], arrFunc[funcIndex].nameFunc);
        else
            printf("%s\n", resultStr);
    }

    return 0;
}