// Arup Guha
// 12/3/2021
// Solution to COP 3502 Fall 2021 Program 6: Priority Hair Salon

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

#define MAX_STYLISTS 10
#define INIT_SIZE 10
#define MAX 20

typedef struct customer {
    char name[MAX+1];
    int gotStylist;
    char prefStylist[MAX+1];
    int loyalty;
    int tCut;
    int timeEntered;
} customer;

typedef struct heap {
    customer** heapArray;
    int capacity;
    int size;
} heap;

typedef struct stylist {
    char name[MAX+1];
    heap* pQueue;
    customer* current;
    int timeFree;
} stylist;

// Functions required to run a heap.
heap* initHeap();
void swap(heap* hPtr, int i, int j);
void percolateUp(heap* hPtr, int index);
void percolateDown(heap* hPtr, int index);
int minimum(customer* c1, int idx1, customer* c2, int idx2);
void insert(heap* hPtr, customer* cPtr);
customer* delMin(heap* hPtr);
int compare(customer* c1, customer* c2);
void freeHeap(heap* hPtr);

// Stylist functions.
void setUpStylist(stylist* sPtr, char* sName);
int numWait(stylist* sPtr);
void addCustomer(stylist* sPtr, customer* cPtr);
int getStylist(stylist dressers[], char person[], int numStylists);
int getSmallestLine(stylist dressers[], int numStylists);
int getNextFinishTime(stylist dressers[], int numStylists);

int main(void) {

    // Get basic info and set up each of the stylists.
    int numCust, numStylists;
    scanf("%d%d", &numCust, &numStylists);
    stylist dressers[MAX_STYLISTS];
    for (int i=0; i<numStylists; i++) {
        char tmp[MAX+1];
        scanf("%s", tmp);
        setUpStylist(&dressers[i], tmp);
    }

    // Where we will store the customers.
    customer** log = malloc(sizeof(customer*)*numCust);

    // Read the customers in.
    for (int i=0; i<numCust; i++) {

        // Make room.
        log[i] = malloc(sizeof(customer));

        // Read everything in.
        scanf("%d%s%s", &(log[i]->timeEntered), log[i]->name, log[i]->prefStylist);
        scanf("%d%d", &(log[i]->loyalty), &(log[i]->tCut));

        // Default this to not getting the stylist.
        log[i]->gotStylist = 0;
    }

    // cIdx is index into log.
    int cIdx = 0;

    // Event loop, we'll get out another way.
    while (1) {

        // Get the next time to enqueue a customer.
        int nextInLine = 2000000000;
        if (cIdx < numCust)
            nextInLine = log[cIdx]->timeEntered;

        // See which line finishes next.
        int nextFinLine = getNextFinishTime(dressers, numStylists);

        // No one to put in line and no one getting hair cut; we're done!
        if (nextFinLine == -1 && nextInLine == 2000000000) break;

        // Process adding someone into a line.
        if (nextFinLine == -1 || nextInLine <= dressers[nextFinLine].timeFree) {

            // First figure out which line to add them into.
            int line = -1;

            // See if their preferred stylist is there.
            if (strcmp(log[cIdx]->prefStylist, "NONE") != 0 &&
                        getStylist(dressers, log[cIdx]->prefStylist, numStylists) >= 0)
                line = getStylist(dressers, log[cIdx]->prefStylist, numStylists);

            // Otherwise, just do the usual rule.
            else
                line = getSmallestLine(dressers, numStylists);

            // Add this customer to line number line. Update index.
            addCustomer(&dressers[line], log[cIdx]);
            cIdx++;
        }

        // Process finishing a haircut.
        else {

            // This is the information requested.
            printf("%s %d %d %s\n", dressers[nextFinLine].current->name,
                   dressers[nextFinLine].timeFree, dressers[nextFinLine].current->loyalty,
                   dressers[nextFinLine].name);

            // Put someone in the chair, if someone is waiting.
            if (dressers[nextFinLine].pQueue->size > 0) {
                dressers[nextFinLine].current = delMin(dressers[nextFinLine].pQueue);
                dressers[nextFinLine].timeFree += dressers[nextFinLine].current->tCut;
                dressers[nextFinLine].current->loyalty += dressers[nextFinLine].current->tCut/10;
            }

            // Otherwise, indicate that no one is in this line.
            else
                dressers[nextFinLine].current = NULL;
        }
    }

    // Clean up time - first each heap.
    for (int i=0; i<numStylists; i++)
        freeHeap(dressers[i].pQueue);

    // Then each customer.
    for (int i=0; i<numCust; i++)
        free(log[i]);

    // Then the customer array.
    free(log);

    return 0;
}

// Returns a pointer to an empty heap.
heap* initHeap() {
    heap* ptr = malloc(sizeof(heap));
    ptr->heapArray = malloc(sizeof(customer*)*(INIT_SIZE+1));
    ptr->capacity = INIT_SIZE;
    ptr->size = 0;
    return ptr;
}

// Frees the dynamically associated memory with the heap.
void freeHeap(heap* hPtr) {
    free(hPtr->heapArray);
    free(hPtr);
}

// Swaps indexes i and j in the heap pointed to by hPtr.
void swap(heap* hPtr, int i, int j) {
    customer* tmp = hPtr->heapArray[i];
    hPtr->heapArray[i] = hPtr->heapArray[j];
    hPtr->heapArray[j] = tmp;
}

// Runs percolate up on the heap pointed to by hPtr from index index.
void percolateUp(heap* hPtr, int index) {

    // Done.
    if (index <= 1) return;

    // We need to go up one level; then recurse.
    if (compare(hPtr->heapArray[index], hPtr->heapArray[index/2]) < 0) {
        swap(hPtr, index, index/2);
        percolateUp(hPtr, index/2);
    }
}

// Runs percolate down on the heap pointed to by hPtr from index index.
void percolateDown(heap* hPtr, int index) {

    // Nothing below me.
    if (2*index > hPtr->size) return;

    // One child only, just see if we should swap with it.
    if (2*index == hPtr->size) {
        if (compare(hPtr->heapArray[index*2], hPtr->heapArray[index]) < 0)
            swap(hPtr, index, index*2);
        return;
    }

    // Get the better of the children.
    int min = minimum(hPtr->heapArray[2*index], 2*index, hPtr->heapArray[2*index+1], 2*index+1);

    // No swap to be made.
    if (compare(hPtr->heapArray[min], hPtr->heapArray[index]) > 0) return;

    // Swap and recursively percolate down.
    swap(hPtr, min, index);
    percolateDown(hPtr, min);
}

// Determines whether c1 or c2 should go first based on priority and returns the corresponding
// index that customer is stored in, either idx1 or idx2, respectively.
int minimum(customer* c1, int idx1, customer* c2, int idx2) {
    if (compare(c1, c2) < 0) return idx1;
    return idx2;
}

// Inserts the customer pointed to by cPtr into the heap pointed to by hPtr.
void insert(heap* hPtr, customer* cPtr) {

    // It's full, expand!
    if (hPtr->size == hPtr->capacity) {
        hPtr->heapArray = realloc(hPtr->heapArray, sizeof(customer*)*(2*hPtr->capacity+1));
        hPtr->capacity *= 2;
    }

    // Add 1 to size, add the item in, and percolate it up!
    hPtr->size++;
    hPtr->heapArray[hPtr->size] = cPtr;
    percolateUp(hPtr, hPtr->size);
}

// Pre-condition: The heap pointed to by hPtr is NOT empty.
// Post-condition: Removes the minimum item in the heap pointed to by hPtr and returns it.
customer* delMin(heap* hPtr) {

    // Save so we can return.
    customer* retval = hPtr->heapArray[1];

    // Mailboy takes the CEO's office!
    hPtr->heapArray[1] = hPtr->heapArray[hPtr->size];

    // One fewer item in the heap.
    hPtr->size--;

    // Mailboy must percolate down...then return the element.
    percolateDown(hPtr, 1);
    return retval;
}

// Returns a negative integer if the customer pointed to by c1 comes before the customer pointed to by c2.
// 0 if they are equal, or a positive integer if the customer pointed to by c1 comes after the customer
// pointed to by c2.
int compare(customer* c1, customer* c2) {

    // First break ties via loyalty.
    if (c1->loyalty != c2->loyalty) return c2->loyalty - c1->loyalty;

    // I got my preferred stylist and you did't.
    if (c1->gotStylist && !c2->gotStylist) return -1;

    // Other way around.
    if (c2->gotStylist && !c1->gotStylist) return 1;

    // Last tiebreaker is name.
    return strcmp(c1->name, c2->name);
}

// Sets up the stylist pointed to by sPtr to have the name sName.
void setUpStylist(stylist* sPtr, char* sName) {
    strcpy(sPtr->name, sName);
    sPtr->pQueue = initHeap();
    sPtr->current = NULL;
    sPtr->timeFree = -1;
}

// Returns the number of people waiting for the stylist pointed to by sPtr.
int numWait(stylist* sPtr) {
    if (sPtr->current == NULL) return -1;
    return sPtr->pQueue->size;
}

// Adds the customer pointed to by cPtr into the "line" for the stylist pointed to by sPtr.
void addCustomer(stylist* sPtr, customer* cPtr) {

    // Update if this customer got their stylist.
    if ( strcmp(cPtr->prefStylist, sPtr->name) == 0) cPtr->gotStylist = 1;

    // No one in chair - go directly to the chair!
    if (sPtr->current == NULL) {
        sPtr->current = cPtr;
        sPtr->timeFree = cPtr->timeEntered + cPtr->tCut;
        cPtr->loyalty += (cPtr->tCut/10);
    }

    // add to queue.
    else
        insert(sPtr->pQueue, cPtr);
}

// If person is working, returns the index person is stored in dressers, otherwise, returns -1.
int getStylist(stylist dressers[], char person[], int numStylists) {

    // Look for this stylist - if we find them, return that index.
    for (int i=0; i<numStylists; i++)
        if (strcmp(dressers[i].name, person) == 0)
            return i;

    // Not working today!
    return -1;
}

// Returns the smallest line index of any of the dressers.
int getSmallestLine(stylist dressers[], int numStylists) {

    // Default to the first.
    int res = 0;
    int numW = numWait(&dressers[0]);

    // Update only if something is strictly better.
    for (int i=1; i<numStylists; i++) {
        if (numWait(&dressers[i]) < numW) {
            numW = numWait(&dressers[i]);
            res = i;
        }
    }

    // Ta da!
    return res;
}

// Returns the index of the hairdresser who is finishing a cut next.
int getNextFinishTime(stylist dressers[], int numStylists) {

    int res = -1, curT = -1;

    // Go through each stylist.
    for (int i=0; i<numStylists; i++) {

        // No one here.
        if (dressers[i].current == NULL) continue;

        // Update if this is the first one or if this is better than what's been seen.
        if (res == -1 || dressers[i].timeFree < curT) {
            res = i;
            curT = dressers[i].timeFree;
        }
    }

    // Ta da!
    return res;
}