/*******************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : LT-2-EVEN-A
* Description : Inverse 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 character corresponding to a string map for a function if found, otherwise return '\0'
char fetchInverseMap(mapFunc *af, int n, char *str)
{
    int i;
    char c = '\0';
    for (i=0; i<n; i++) {
        if(!strcmp(af[i].rhs, str)) {
            c = af[i].lhs;
            break;
        }
    }
    return c;
}

int main()
{
    char tempStr[MAX_STRING];
    char *resultStr;
	char *mapStr, mapChar = '\0';
    int numFunc, numExample, i, j, k, l, m, n, 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 Inverse-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);
					mapStr = (char *)malloc((resultStrLen+1)*sizeof(char));
                    for (k=0,m=0,n=0,tempStr[0]='\0'; k<resultStrLen; k++) { // iterating over each string and mapping it
						mapStr[n] = resultStr[k];
						mapStr[n+1] = '\0';
                        mapChar = fetchInverseMap(arrFunc[funcIndex].arrMap, arrFunc[funcIndex].numMap, mapStr);
						if(mapChar != '\0') {
                            tempStr[m] = mapChar;
							m++;
							n = 0;
						}
						else{
							n++;
						}
                    }
					tempStr[m] = '\0';
                    if (mapChar == '\0') break;
                    strcpy(resultStr, tempStr);
                }
            }
            if (mapChar == '\0') 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 (mapChar == '\0') // character map is not defined for the given function
            printf("Inverse-Homomorphism for '%s' in Function '%s' is Undefined! (ERROR)\n", mapStr, arrFunc[funcIndex].nameFunc);
        else
            printf("%s\n", resultStr);
    }

    return 0;
}