from heapq import *
class DinnerPlates(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.stack = []
        self.c = capacity
        self.idx = [] #ڴпλջ±

    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        if self.idx:
            index = heappop(self.idx) #СĿյջ±
            self.stack[index].append(val) #val
            if len(self.stack[index]) < self.c: #֮ûͰյջ±Žself.idx
                heappush(self.idx, index)
        else: #ջˣֻһջĩβ
            self.stack.append([val])
            if self.c > 1:
                self.idx.append(len(self.stack) - 1)
            

    def pop(self):
        """
        :rtype: int
        """
        while self.stack and not self.stack[-1]:
            self.stack.pop()
        if not self.stack: #еջǿյ
            return -1
        else:
            if len(self.stack[-1]) == self.c: #ջ
                heappush(self.idx, len(self.stack) - 1) #Ҫпλջ
            return self.stack[-1].pop()
            
    def popAtStack(self, index):
        """
        :type index: int
        :rtype: int
        """
        if index >= len(self.stack): #±Խ
            return -1
        else:
            s = self.stack[index] # ±Ϊindexջȡ
            if len(s) == self.c: #ջ
                heappush(self.idx, index) #Ҫ
            return s.pop() if s else -1 #ջǿյģ-1 򷵻pop


# Your DinnerPlates object will be instantiated and called as such:
# obj = DinnerPlates(capacity)
# obj.push(val)
# param_2 = obj.pop()
# param_3 = obj.popAtStack(index)