class WebpagePriorityQueue:
    def __init__(self, q, indexes):
        #The query is saved as a list of strings
        self.query = parsequery(q)
        self.count = len(indexes)
        self.data = self.heapify(self.query, indexes)

    def peek(self):
        return self.data[0]

    #Extracts the top value and shifts down
    def poll(self):
        if self.count <= 0:
            print('Cannot pop from empty queue')
        else:
            #Returns the 'top' item of the heap, which
            #is the first element of the list
            ret = self.data[0]
            #Temporarily assigns the last element of the
            #list as the head
            self.data[0] = self.data[self.count - 1]
            self.count -= 1
            #Shifts the new head element down the heap
            self.shiftdown(0)
            return ret

    #Builds a maxheap using the provided indexes and
    #the query phrase
    def heapify(self, indexes):
        tempheap = []
        for index in indexes:
            #Append the index and ensure the heap is valid
            tempheap.append(index)
            self.shiftup(self.count - 1)
        return tempheap

    #Both shifts are based on the priority value of the index
    #calculated with the given query
    def shiftup(self, i):
        #Calculate the index of the parent node
        p = (i - 1) >> 1 #Use shift to perform integer division
        #While the child priority is higher than the parent's:
        while i > 0 and calcPrio(self.query, self.data[p]) < calcPrio(self.query, self.data[i]):
            #Swap the child and parent and move upwards
            temp = self.data[i]
            self.data[i] = self.data[p]
            self.data[p] = temp
            #Repeat shiftup on the parent node
            i = p
            #Calculate the new parent index value
            p = (i - 1) >> 1

    def shiftdown(self, i):
        #Calculate the index of the left child node
        c = 2 * i + 1
        while c < self.count:
            if c + 1 < self.count and calcPrio(self.query, self.data[c+1]) > calcPrio(self.query, self.data[c]):
                #If left child is not larger, checks if right child exists
                c += 1
            if calcPrio(self.query, self.data[i]) >= calcPrio(self.query, self.data[c]):
                #If current has higher priority than the child, stop
                break
            #Swap the current node with the larger of its child nodes
            temp = self.data[i]
            self.data[i] = self.data[c]
            self.data[c] = temp
            #Repeat shiftdown on the child node
            i = j
            #Calculate the new child index value
            j = 2 * i + 1

    #This should be done using an in-place heapsort, but
    #I did not have the time :(
    def reheap(self, newQ):
        #Parses the new query and builds a new maxheap
        self.query = parsequery(newQ)
        return self.heapify(self.query, self.data)

#Helper function which parses the query string
#into a list of strings delimited by spaces
def parsequery(string):
    allowed = 'abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    tempS = ''
    for c in string:
        if c in allowed:
            tempS += c.lower()
    return tempS.split(' ')

#Helper function that calculates the priority
#of an WebPageIndex object based on a query
def calcPrio(query, index):
    p = 0
    for q in query:
        p += index.getCount(q)
    return p