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

// Node of a list
typedef struct NodeT {
  char data;
  struct NodeT * next;
} Node;

// List with a pointer to the first (head) and the last (foot)
// element of the list
typedef struct ListT {
  Node * head;
  Node * foot;
} List;


// create a new list and return the pointer to the list
List * makeNewList ();


// insert a new item at the head of the list
void insertAtHead (List *list, char newItem);

// free list: free every node and the list structure itself
void freeList (List *list); 

// pretty print list
void printList (List *list);
           
int lengthOfList (List *list);



int main (int argc, char ** argv) {
   int i=0;
   int k=0;
   int j=0;
   int h=0;
   char d;
   char c;
   int userInput[20];
   int replaceInput[20];
   int ruleInput[20];
   int Output[20];
   int f=0;
/////////////////////make this a function start  -- this is the input function (grammar.txt)
   while((c = getchar()) != '\n'){
//      List *list = makeNewList();
      userInput[i]=c;
      i++;
      f++;
//      lengthOfList (list);
//      freeList (list);
   }  
   h=i;   //number of characters that go in
   List *inputList = makeNewList();
   while (k<i){
      while (i>j){
         insertAtHead (inputList, userInput[i-1]);
         i--;
      }
      k++;
   }
   printList (inputList);
///////////////////////make this a function end   
  
    

///////////////////////make this a function start --- This is the output function (prints out after rules)     
      
//   char f;



///////////////////////make this a function end                                                         





  
//////////////////////Make this a function start -- this is the replacing function
   i=0;
   while ((d = getchar()) != '\n'){
      replaceInput[i]=d;
      i++;   
   }
   k=0;
   j=0;
   List *replaceList = makeNewList();
   while (k<i){
      while (i>j){
         insertAtHead (replaceList, replaceInput[i-1]);
         i--;
      }
      k++;
   }        
   printList (replaceList);
//////////////////////Make this a function start  -- this is the rule function (what rules you want)
   i=0;
   char e;
   while ((e =getchar()) != '\n'){
      ruleInput[i]=e;
      i++;
   }

   k=0;
   j=0;
   List *ruleList = makeNewList();

      while (i>j){
         insertAtHead (ruleList, ruleInput[i-1]);
         i--;
      }

   printList (ruleList);
///////////////////////make this a function end 
   List *newList = makeNewList();
   Node *currentNode=NULL;
   Node *replaceNode;
   Node *ruleNode=NULL;
//   Node *newNode=NULL;
   assert(inputList);
   assert(replaceList);
   assert(ruleList);
   currentNode = inputList->head;      //currentnode is the input node
   replaceNode = replaceList->head;
   ruleNode = ruleList->head;
   i=h;

   while (currentNode){ 
//        printf("currentNode is %c and replaceNode is %c\n", currentNode->data,replaceNode->data);
      if (currentNode->data != replaceNode->data){
//        printf("Then newNode = currentNode\n");
//         newNode = currentNode;     
         Output[i-1]=currentNode->data;
//         printf("output is: %c\n", Output[i]);
         insertAtHead (newList, Output[i-1]); 
//        printf("the print list is");
printf("i is: %d",i);
         i--;
      } else { 
//        printf("Else newNode = ruleNode\n");
//      newNode = ruleNode;
        Output[i-1]=ruleNode->data;
//        printf("output is: %c\n", Output[i]);
        insertAtHead (newList, Output[i-1]);
        free(replaceNode);
        replaceNode = replaceNode->next;
printf("i is: %d",i);       
//        newNode=newNode->next;
        i--;
      }      
      printList(newList);
      currentNode = currentNode->next;
   }
       
        printList(newList);

//////////////////////Make this a function end 

  
   return (0);

}



List * makeNewList () {
  // allocate space for the List struct
  List * l = (List*) malloc (sizeof(List));
  // check if assert was succesfull
  assert (l); 
  // list is empty, so head and foot don't point to a node yet
  l->head = NULL;
  l->foot = NULL;
  // return the list pointer
  return (l);
}


void insertAtHead (List *list, char newItem) {
  // allocate space for the new node struct
  Node * node = (Node *) malloc (sizeof(Node));
  // check if assert was succesfull
  assert (node);
  // initialise data field of the node
  node->data = newItem; 
  // make sure the list pointer is not NULL
  assert (list);
  // let node point to first node in list
  node->next = list->head; 
  // the new head of the list is the new node
  list->head = node;
  // if list was empty, foot is still NULL, and 
  // head and foot should point to the same node
  // since the list has only one element now
  if (list->foot == NULL) {
    list->foot = node; 
  }
}

void freeList (List *list) {
   Node *copyNode;
   Node *currentNode;
   assert(list);
   currentNode = list->head;
   while (currentNode) {
      currentNode = currentNode->next;
      copyNode = currentNode;
      free (currentNode);
      currentNode = copyNode;
   }
}


void printList (List *list) {
  Node *currentNode;
  // make sure list is not NULL
  assert (list);
  // keep track of the current node we're printing
  currentNode = list->head;
  printf ("{");
  while (currentNode) {
    // print data of current node
    printf ("%c", currentNode->data);
    // move currentNode to the next node
    currentNode = currentNode->next;
    // printf ',' only if this was not the last node
    if (currentNode) {
      printf (", ");
    }
  }
  printf ("}\n");  

}

int lengthOfList (List *list) {
   Node *currentNode;
   assert(list);
   currentNode = list->head;
   int counter=0;
   while (currentNode) {
      counter++;
      currentNode = currentNode->next;
   }
   printf ("The list is of length: %d\n",counter);
return (0);
}