// Arup Guha
// 9/24/2023
// Solution to Fall 2023 COP 3502 Program 2: Movie Ticketing Queue

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

#define MAX 51
#define MAXTIME 2000000000
#define NUMQS 12
#define NONE -1

typedef struct customer {
    char* name;
    int arriveT;
    int checkoutT;
    int linenum;
} customer;

typedef struct node {
    customer* cPtr;
    struct node* next;
} node;

typedef struct queue {
    node* front;
    node* back;
    int size;
} queue;


// Functions associated with a queue.
queue* makeNewQueue();
void enqueue(queue* qPtr, customer* cust);
customer* dequeue(queue* qPtr);
customer* peek(queue* qPtr);
int empty(queue* qPtr);
int size(queue* qPtr);
int getFrontArrivalTime(queue* qPtr);

// Functions for simulation.
int* getNonEmpty(queue* lines[], int* numNonEmpty);
customer* makeCustomer(char* name, int numTickets, int timeArrive, queue* lines[]);
int getNext(queue* lines[], int* myqueues, int sI, int eI);
int getLine(queue* lines[], char* name);

int main() {

    // Set up the 12 queues.
    queue* lines[NUMQS];
    for (int i=0; i<NUMQS; i++)
        lines[i] = makeNewQueue();

    // Read in # of operations and number of booths.
    int numOps, numBooths;
    scanf("%d%d", &numOps, &numBooths);

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

        // Get the info.
        char name[MAX];
        int numTickets, timeArrive;
        scanf("%s%d%d", name, &numTickets, &timeArrive);

        // Make a customer...we need the lines to figure out where the customer will go.
        customer* tmp = makeCustomer(name, numTickets, timeArrive, lines);

        // Enqueue this person in the appropriate queue.
        enqueue(lines[tmp->linenum], tmp);
    }

    // Get the list of the queues that are non-empty.
    int numNonEmpty;
    int* myqueues = getNonEmpty(lines, &numNonEmpty);

    // Minimum # of queues per booth.
    int each = numNonEmpty/numBooths;
    int getExtra = numNonEmpty%numBooths;

    // Index into myqueues.
    int j = 0;

    // Loop through the booths.
    for (int i=0; i<numBooths; i++) {

        // Booth header.
        printf("Booth %d\n", i+1);

        // Current time for this booth simulation.
        int curT = 0;

        // Figure out # of queues.
        int need = each;
        if (i<getExtra) need++;

        // Process.
        int nextPerson = getNext(lines, myqueues, j, j+need);
        while (nextPerson != NONE) {

            // Dequeue the appropriate person.
            customer* tmp = dequeue(lines[nextPerson]);

            // Update time if necessary.
            if (tmp->arriveT > curT)
                curT = tmp->arriveT;

            // Get the time this person's checking out.
            curT += tmp->checkoutT;

            // This is what's required.
            printf("%s from line %d checks out at time %d.\n", tmp->name, tmp->linenum+1, curT);

            // Free memory for this customer.
            free(tmp->name);
            free(tmp);

            // Get next.
            nextPerson = getNext(lines, myqueues, j, j+need);
        }

        // Update where we start in myqueues
        j += need;
        printf("\n");
    }

    // Free all the queues.
    for (int i=0; i<NUMQS; i++)
        free(lines[i]);
    free(myqueues);

    return 0;
}

// Returns a pointer to a newly created customer with the name , numTickets and arrival time passed in.
customer* makeCustomer(char* name, int numTickets, int timeArrive, queue* lines[]) {

    // Set up this customer.
    customer* tmp = malloc(sizeof(customer));
    tmp->checkoutT = 30 + numTickets*5;
    tmp->arriveT = timeArrive;

    // Make just the right amount of space.
    tmp->name = calloc(strlen(name)+1, sizeof(char));
    strcpy(tmp->name, name);

    // Update the line number...
    tmp->linenum = getLine(lines, name);

    // Return a pointer to the created customer.
    return tmp;
}

// Returns the line for the person with name for the set of lines.
int getLine(queue* lines[], char* name) {

    int value = (name[0]-'A')%13;

    // Return the 0-based line number here.
    if (value != 0) return value-1;

    int res = NONE;

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

        // Skip over the empty ones.
        if (empty(lines[i])) continue;

        // Update if this one's shorter.
        if (res == NONE || size(lines[i]) < size(lines[res]))
            res = i;
    }

    // This is if all lines are empty.
    if (res == NONE) return 0;

    // Ta da!
    return res;
}

// Returns the 0-based line number of the person who arrives earliest from the queue numbers
// stored in myqueues[sI,eI-1].
int getNext(queue* lines[], int* myqueues, int sI, int eI) {

    int res = NONE;
    int early = NONE;

    // Loop through the range of queues we're looking at.
    for (int i=sI; i<eI; i++) {

        // The queue number we're looking at.
        int idx = myqueues[i];

        // This one's empty.
        if (empty(lines[idx])) continue;

        // Time for an update.
        if (res == NONE || getFrontArrivalTime(lines[idx]) < early) {
            res = idx;
            early = getFrontArrivalTime(lines[idx]);
        }
    }

    // This it the earliest person in the range of lines queried.
    return res;
}

// Returns an array storing the 0-based numbers of each non-empty queue, in order and also stores the number of these
// non-empty queues in the integer pointed to by numNonEmpty.
int* getNonEmpty(queue* lines[], int* numNonEmpty) {

    // Store result here.
    int* res = calloc(NUMQS, sizeof(int));

    // Index into res.
    int j = 0;

    // Loop through queues.
    for (int i=0; i<NUMQS; i++) {

        // Add line i to our list if it's non-empty.
        if (!empty(lines[i])) {
            res[j] = i;
            j++;
        }
    }

    // Update these before returning res.
    *numNonEmpty = j;
    res = realloc(res, j*sizeof(int));
    return res;
}

// Returns an empty queue.
queue* makeNewQueue() {
    queue* ptr = malloc(sizeof(queue));
    ptr->front = NULL;
    ptr->back = NULL;
    ptr->size = 0;
    return ptr;
}

// Enqueues the customer pointed to by cust to the queue pointed to by qPtr.
void enqueue(queue* qPtr, customer* cust) {

    // Create the new node.
    node* tmp = malloc(sizeof(node));
    tmp->cPtr = cust;
    tmp->next = NULL;

    // Only time front gets updated.
    if (qPtr->front == NULL)
        qPtr->front = tmp;

    // For non-empty lists, we must link from old back to new node.
    else
        qPtr->back->next = tmp;

    // We always have to do this.
    qPtr->back = tmp;
    qPtr->size++;
}

// Dequeues the front item in the queue pointed to by qPtr and returns a pointer to this customer.
customer* dequeue(queue* qPtr) {

    // Should never happen, but to be safe.
    if (qPtr->front == NULL) return NULL;

    // These will be helpful.
    node* tmp = qPtr->front;
    customer* retval = tmp->cPtr;

    // Special case, go down to empty.
    if (qPtr->front == qPtr->back) qPtr->back = NULL;

    // We always do this.
    qPtr->front = qPtr->front->next;
    qPtr->size--;

    // We don't need this memory.
    free(tmp);

    // This is the pointer we return.
    return retval;
}

// Returns a pointer to the customer at the front of the queue.
customer* peek(queue* qPtr) {

    // To be safe.
    if (qPtr->front == NULL) return NULL;

    // Return a pointer to the customer at the front of the queue.
    return qPtr->front->cPtr;
}

// Returns true iff the queue pointed to by qPtr is empty.
int empty(queue* qPtr) {
    return size(qPtr) == 0;
}

// Returns the size of the queue pointed to by qPtr.
int size(queue* qPtr) {
    return qPtr->size;
}

// Gets the arrival time of the person in the front of the queue. Returns MAXTIME otherwise.
int getFrontArrivalTime(queue* qPtr) {
    customer* tmp = peek(qPtr);
    if (tmp == NULL) return MAXTIME;
    return tmp->arriveT;
}