#include <iostream>
#include <string>
#include <cassert>

using namespace std;

struct Qnode{
    string val;
    Qnode* next;
};

struct Queue{
    Qnode *first;
    Qnode *last;
};

struct PQnode{
    int priority;
    Queue q;
    PQnode* next;
};

typedef PQnode* PQ;

void initPQ (PQ& pq) {
    pq = NULL;
}

bool isEmptyPQ (const PQ& pq){
    return NULL == pq;
}

void enterPQ (PQ& pq, string val, int priority) {
    Qnode *newQnode = new Qnode;
    newQnode->val = val;
    newQnode->next = NULL;
    if(isEmptyPQ(pq) || priority < pq->priority){
        PQnode *newpq = new PQnode;
        newpq->priority = priority;
        newpq->next = NULL;
        newpq->q.first = newQnode;
        newpq->q.last = newQnode;
        newpq->next = pq;
        pq = newpq;
    }else{
        PQnode *temp = pq;
        while(temp->next!=NULL && temp->next->priority <= priority){
            temp = temp->next;
        }
        if(temp->priority == priority){
            temp->q.last->next = newQnode;
            temp->q.last = newQnode;
        }else{
            PQnode *newpq = new PQnode;
            newpq->priority = priority;
            newpq->next = NULL;
            newpq->q.first = newQnode;
            newpq->q.last = newQnode;
            if(temp->next != NULL){
                newpq->next = temp->next;
            }
            temp->next = newpq;
        }
    }
}

string firstPQ (const PQ& pq){
    assert (!isEmptyPQ(pq));
    return(pq->q.first->val);
}

void leavePQ (PQ& pq) {
    assert (!isEmptyPQ(pq));
    if(pq->q.first->next == NULL){
        PQnode *temppq = pq;
        pq=pq->next;
        delete temppq->q.first;
        delete temppq;
    }else{
        Qnode *temp = pq->q.first;
        pq->q.first = pq->q.first->next;
        delete temp;
}

int sizePQ (const PQ& pq) {
    if (isEmptyPQ(pq)) {
        return 0;
    }
    int numPQ = 0;
    PQnode *temp = pq;
    while(temp!= NULL){
        Qnode *tempQ = temp->q.first;
        //cout << "Blah: " << tempQ->val << endl;
        while(tempQ!=NULL){
            //cout << tempQ->val << endl;
            numPQ++;
            tempQ = tempQ->next;
        }
        temp = temp->next;
    }
    return numPQ;
}

int sizeByPriority (const PQ& pq, int priority) {
    if (isEmptyPQ(pq)) {
        return 0;
    }
    int numPQ = 0;
    PQnode *temp = pq;
    while(temp->next!=NULL && temp->next->priority <= priority){
        temp = temp->next;
    }
    if (NULL == temp || temp->priority != priority) {
        return 0;
    }
    Qnode *tempQ = temp->q.first;
    while(tempQ!=NULL){
        numPQ ++;
        tempQ = tempQ->next;
    }
    return numPQ;
}

int numPriorities (const PQ& pq) {
    if (isEmptyPQ(pq)) {
        return 0;
    }
    int numPQ = 0;
    PQnode *temp = pq;
    while(temp!=NULL){
        numPQ ++;
        temp = temp->next;
    }
    return numPQ;
}

void CGprint(const PQ& pq){
    PQ temp=pq;
    while(temp!=NULL){
        //cout<<"priority "<<temp->priority<<". Priority size: "<<sizeByPriority(pq, temp->priority)<<" :"<<endl;
        Qnode* iter=temp->q.first;
        while(iter!=NULL){
            cout<<iter->val<<endl;
            iter=iter->next;
        }
        temp=temp->next;
    }
}