You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.
Implement the DinnerPlates class:

DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
void push(int val) Pushes the given positive integer val into the leftmost stack with size less than capacity.
int pop() Returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
int popAtStack(int index) Returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index is empty.

Example:
Input: 
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
Output: 
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

Explanation: 
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.

 
Constraints:

1 <= capacity <= 20000
1 <= val <= 20000
0 <= index <= 100000
At most 200000 calls will be made to push, pop, and popAtStack.

Difficulty: interview

Starter code:

class DinnerPlates:
    def __init__(self, capacity: int):
    def push(self, val: int) -> None:
    def pop(self) -> int:
    def popAtStack(self, index: int) -> int:
# 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)

Solutions:
from heapq import heapify, heappush, heappop 
class DinnerPlates:
        # index * cap ->  access start of stack at index
        # index * cap + (cap - 1)  -> access last element of stack at index
        
    def __init__(self, capacity: int):
        self.stack = [] # just one array to simulate all the stacks
        self.cap = capacity 
        self.idx = [] # min-heap to track empty indicies
        
    def push(self, val: int) -> None:
        if len(self.idx) > 0:
            while len(self.idx) > 0:
                i = heappop(self.idx) 
                # Given that we just push index but don't validate the cache while
                # poping we need to check if this index is within current limits
                if i < len(self.stack):
                    self.stack[i] = val
                    return 
                
        # we didn't find empty spaces so we add to the end
        self.stack.append(val)

    def pop(self) -> int:
        n = len(self.stack) - 1
        if n < 0:
            return -1
        
        while n > -1:
            if self.stack[n] != -1:
                v = self.stack[n]
                self.stack[n] = -1
                # Add the empty index to the heap
                heappush(self.idx , n)
                return v
            else:
                # Because those appear at the end the list we free those memory spaces so
                # later pop operations are optimized
                del(self.stack[n])
            n -= 1
            
        # All stacks are empty
        return -1
        
        

    def popAtStack(self, index: int) -> int:
        # additional check that is [optional] just to skip any effort 
        # if index is already out of current limits
        count = len(self.stack) // self.cap
        if index > count:
            return -1
        
        # capture the boundaries of this stack
        leftptr = (index * self.cap) 
        rightptr = leftptr + self.cap - 1
        if rightptr > (len(self.stack) - 1): # edge case
            rightptr = (len(self.stack) - 1)
            
        # traverse within the stack at this index until we empty it or we find an occupied location    
        while self.stack[rightptr] == -1 and rightptr >= leftptr:
            rightptr -=1
            
        # if it isn't empty it means we found occupied position
        if rightptr >= leftptr:
            v = self.stack[rightptr]
            self.stack[rightptr] = -1
            # Add the empty index to the heap
            heappush(self.idx , rightptr)
            return v
        else:
            return -1


from heapq import heapify, heappush, heappop 
class DinnerPlates:
        # index * cap ->  access start of stack at index
        # index * cap + (cap - 1)  -> access last element of stack at index
        
    def __init__(self, capacity: int):
        self.stack = [] # just one array to simulate all the stacks
        self.cap = capacity 
        self.idx = [] # min-heap to track empty indicies
        
    def push(self, val: int) -> None:
        if len(self.idx) > 0:
            while len(self.idx) > 0:
                i = heappop(self.idx) 
                # Given that we just push index but don't validate the cache while
                # poping we need to check if this index is within current limits
                if i < len(self.stack):
                    self.stack[i] = val
                    return 
                
        # we didn't find empty spaces so we add to the end
        self.stack.append(val)

    def pop(self) -> int:
        n = len(self.stack) - 1
        if n < 0:
            return -1
        
        while n > -1:
            if self.stack[n] != -1:
                v = self.stack[n]
                self.stack[n] = -1
                # Add the empty index to the heap
                heappush(self.idx , n)
                return v
            else:
                # Because those appear at the end the list we free those memory spaces so
                # later pop operations are optimized
                del(self.stack[n])
            n -= 1
            
        # All stacks are empty
        return -1
        
        

    def popAtStack(self, index: int) -> int:
        # additional check that is [optional] just to skip any effort 
        # if index is already out of current limits
        count = len(self.stack) // self.cap
        if index > count:
            return -1
        
        # capture the boundaries of this stack
        leftptr = (index * self.cap) 
        rightptr = leftptr + self.cap - 1
        if rightptr > (len(self.stack) - 1): # edge case
            rightptr = (len(self.stack) - 1)
            
        # traverse within the stack at this index until we empty it or we find an occupied location    
        while self.stack[rightptr] == -1 and rightptr >= leftptr:
            rightptr -=1
            
        # if it isn't empty it means we found occupied position
        if rightptr >= leftptr:
            v = self.stack[rightptr]
            self.stack[rightptr] = -1
            # Add the empty index to the heap
            heappush(self.idx , rightptr)
            return v
        else:
            return -1

from heapq import heappush, heappop
class DinnerPlates:

    def __init__(self, capacity: int):
        self.indicies = []
        self.stacks = []
        self.cap = capacity
    
    def clean_stack(self):
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
            
    def push(self, val: int) -> None:
        while self.indicies:
            index = heappop(self.indicies)
            
            if index < len(self.stacks) and len(self.stacks[index]) < self.cap:
                self.stacks[index].append(val)
                return
        
        if self.stacks and len(self.stacks[-1]) < self.cap:
            self.stacks[-1].append(val)
        else:
            self.stacks.append([val])
        
    def pop(self) -> int:
        if not self.stacks:
            return -1
        else:
            res = self.stacks[-1].pop()
        
        if not self.stacks[-1]:
            self.clean_stack()
        else:
            heappush(self.indicies, len(self.stacks) - 1)
        
        return res

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks) or not self.stacks[index]:
            return -1
        
        res = self.stacks[index].pop()
        
        if not self.stacks[-1]:
            self.clean_stack()
        else:
            heappush(self.indicies, index)
        
        return res
        


# 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)


import collections
import heapq

StackAndFlags = collections.namedtuple('StackAndFlags', [
    'stack', 'on_push_heap', 'on_pop_heap'])

class DinnerPlates:

    def __init__(self, capacity: int):
        self._cap = capacity
        self._stacks = []
        self._next_push_heap = []
        self._next_pop_heap = []
        
    def _push_to_top(self, val):
        i = self._next_push_heap[0]
        assert self._stacks[i].on_push_heap
        self._stacks[i].stack.append(val)
        if len(self._stacks[i].stack) == self._cap:
            self._stacks[i] = self._stacks[i]._replace(on_push_heap=False)
            heapq.heappop(self._next_push_heap)
        if not self._stacks[i].on_pop_heap:
            self._stacks[i] = self._stacks[i]._replace(on_pop_heap=True)
            heapq.heappush(self._next_pop_heap, -i)

    def push(self, val: int) -> None:
        if not self._next_push_heap:
            self._stacks.append(StackAndFlags([], True, True))
            new_i = len(self._stacks) - 1
            heapq.heappush(self._next_push_heap, new_i)
            heapq.heappush(self._next_pop_heap, -new_i)
        self._push_to_top(val)

    def pop(self) -> int:
        i = -1
        while self._next_pop_heap:
            j = -self._next_pop_heap[0]
            if self._stacks[j].stack:
                i = j
                break
            else:
                heapq.heappop(self._next_pop_heap)
                self._stacks[j] = self._stacks[j]._replace(on_pop_heap=False)
        if i < 0:
            return -1
        return self.popAtStack(i)

    def popAtStack(self, index: int) -> int:
        if index >= len(self._stacks) or not self._stacks[index].stack:
            return -1
        ret = self._stacks[index].stack.pop()
        if not self._stacks[index].on_push_heap:
            self._stacks[index] = self._stacks[index]._replace(on_push_heap=True)
            heapq.heappush(self._next_push_heap, index)
        return ret

# 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)


from collections import deque
import heapq

class DinnerPlates:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacklist = []
        self.minh = []

    def push(self, val: int) -> None:
        while len(self.minh) > 0:
            lms = heapq.heappop(self.minh)
            if len(self.stacklist) - 1 >= lms:
                self.stacklist[lms].append(val)
                break
        else:
            if len(self.stacklist) == 0 or len(self.stacklist[-1]) >= self.capacity:
                self.stacklist.append(deque())
            self.stacklist[-1].append(val)

    def pop(self) -> int:
        if len(self.stacklist) == 0:
            return -1

        while len(self.stacklist[-1]) == 0:
            del self.stacklist[-1]

        if len(self.stacklist) > 0:
            res = self.stacklist[-1].pop()
        else:
            res = -1

        if len(self.stacklist[-1]) == 0:
            del self.stacklist[-1]

        return res

    def popAtStack(self, index: int) -> int:
        if len(self.stacklist) - 1 < index or len(self.stacklist[index]) == 0:
            return -1
        else:
            res = self.stacklist[index].pop()
            heapq.heappush(self.minh, index)
            return res


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = [[]]
        self.current = 0
        self.capacity = capacity
        self.tail = 0
        
    def push(self, val: int) -> None:
        while self.current < len(self.stacks) and len(self.stacks[self.current])==self.capacity:
            self.current += 1
        if self.current == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.current].append(val)

    def pop(self) -> int:
        rightmost = len(self.stacks) - 1
        
        while rightmost>=0 and not self.stacks[rightmost]:
            rightmost -= 1
        if rightmost == -1:
            return -1
        elem = self.stacks[rightmost][-1]
        self.stacks[rightmost].pop()
        while rightmost>=0 and not self.stacks[rightmost]:
            self.stacks.pop()
            rightmost -= 1
        return elem
        
    def popAtStack(self, index: int) -> int:
        if index >=len(self.stacks) or not self.stacks[index]:
            return -1
        elem = self.stacks[index][-1]
        self.stacks[index].pop()
        if self.current > index:
            self.current = index
        return elem

# 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)


import heapq
class DinnerPlates:

    def __init__(self, capacity: int):
        self.heap=[]
        self.plates=[]
        self.capacity=capacity
        self.current=None
    def push(self, val: int) -> None:
        # print(\"push\",val, self.plates)
        if len(self.heap)==0:
            if len(self.plates)==0 or len(self.plates[-1])==self.capacity:
                self.plates.append([])
            self.plates[-1].append(val)
            self.current=len(self.plates)-1

        else:
            p=heapq.heappop(self.heap)
            self.plates[p].append(val)

    def pop(self) -> int:
        # print(\"pop\", self.plates)

        for i in range(self.current,-1,-1):
            if len(self.plates[i])!=0:
                self.current=i
                return self.plates[i].pop()
            self.current=0
        return -1
        # if len(self.plates)==0:
        #     return -1
        # p=self.plates[-1][-1]
        # self.plates[-1].pop()
        # # if len(self.plates[-1])==0:
        # #     self.plates.pop()
        # return p
    def popAtStack(self, index: int) -> int:
    
        # print(\"popAtStack\",index, self.plates)
        if len(self.plates)-1<index or len(self.plates[index])==0:
            return -1
        # 3 3
        p=self.plates[index].pop()
        heappush(self.heap, index)
        return p


# 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)


# 1 2
# 3 3
# 5 5
# 5  
# 6 7




class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.availIndexes = []
        self.capacity = capacity
      

    def push(self, val: int) -> None:
        # find the first available one 
        while self.availIndexes and self.availIndexes[0]<len(self.stacks) and len(self.stacks[self.availIndexes[0]])==self.capacity:
            heappop(self.availIndexes)
        if not self.availIndexes:
            heappush(self.availIndexes,len(self.stacks))
        if self.availIndexes[0]==len(self.stacks):
            self.stacks.append([])
        self.stacks[self.availIndexes[0]].append(val)

      

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
            self.availIndexes.remove(len(self.stacks))
        return self.popAtStack(len(self.stacks)-1)
    

    def popAtStack(self, index: int) -> int:
        if 0<=index<len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.availIndexes,index)
            return self.stacks[index].pop()
        return -1
        


# 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)


from collections import deque
import heapq
class DinnerPlates :
    
    def __init__(self,capacity) :
        self.capacity = capacity
        self.plates = deque([deque([],maxlen=capacity)])
        self.popHeap = []
        self.pushHeap = [0]

    def push(self, val : int) -> None :
        while self.pushHeap and (self.pushHeap[0] >= len(self.plates) or len(self.plates[self.pushHeap[0]]) == self.capacity ): 
            heapq.heappop(self.pushHeap)
        if not self.pushHeap :
            self.plates.append(deque(maxlen=self.capacity)) 
            self.pushHeap = [len(self.plates)-1]
        i = self.pushHeap[0]
        self.plates[i].append(val)
        heapq.heappush(self.popHeap,-i)
        return

    def pop(self) -> int :
        while self.popHeap and (-self.popHeap[0] >= len(self.plates) or len(self.plates[-self.popHeap[0]]) == 0 ):
            heapq.heappop(self.popHeap)
        if not self.popHeap : return -1 
        i = -self.popHeap[0]
        return self.plates[i].pop()
        
    def popAtStack(self, index : int) -> int :
        if index >= len(self.plates) or not self.plates[index] : return -1
        val = self.plates[index].pop()
        if self.plates[index] :
            heapq.heappush(self.popHeap,-index)
        heapq.heappush(self.pushHeap,index)
        return val



class DinnerPlates:

    def __init__(self, capacity: int):
        self.stack = []
        self.leftmost = [0]
        self.rightmost = []
        self.capacity = capacity
        self.leftmostset = set([0])
        self.rightmostset = set()
        

    def push(self, val: int) -> None:
        # print(\"leftmost:\", self.leftmost)
        idx = self.leftmost[0]
        if idx >= len(self.stack):
            self.stack.append([val])
        else:
            self.stack[idx].append(val)
        if len(self.stack[idx]) == self.capacity:
            heapq.heappop(self.leftmost)
            self.leftmostset.remove(idx)
        if len(self.leftmost) == 0:
            heapq.heappush(self.leftmost, idx + 1)
            self.leftmostset.add(idx + 1)
        if idx * (-1) not in self.rightmostset:
            heapq.heappush(self.rightmost, idx * (-1))
            self.rightmostset.add(idx * (-1))
        # print(self.stack)

    def pop(self) -> int:
        # print(\"rightmost:\", self.rightmost)
        if len(self.rightmost) == 0:
            return -1
        idx = self.rightmost[0] * (-1)
        val = self.stack[idx].pop()
        if len(self.stack[idx]) == 0:
            heapq.heappop(self.rightmost)
            self.rightmostset.remove(idx * (-1))
        if idx not in self.leftmostset:
            heapq.heappush(self.leftmost, idx)
            self.leftmostset.add(idx)
        # print(self.stack)
        return val
        
    def popAtStack(self, index: int) -> int:
        if index >= len(self.stack) or len(self.stack[index]) == 0:
            return -1
        val = self.stack[index].pop()
        if len(self.stack[index]) == 0:
            self.rightmostset.remove(index * (-1))
            self.rightmost.remove(index * (-1))
        if index not in self.leftmostset:
            heapq.heappush(self.leftmost, index)
            self.leftmostset.add(index)
        # print(self.stack)
        return val
        
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.availIndexes = []
        self.capacity = capacity
      

    def push(self, val: int) -> None:
        # find the first available one 
        while self.availIndexes and self.availIndexes[0]<len(self.stacks) and len(self.stacks[self.availIndexes[0]])==self.capacity:
            heappop(self.availIndexes)
        if not self.availIndexes:
            heappush(self.availIndexes,len(self.stacks))
        if self.availIndexes[0]==len(self.stacks):
            self.stacks.append([])
        self.stacks[self.availIndexes[0]].append(val)

      

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
            # self.availIndexes.remove(len(self.stacks))
        return self.popAtStack(len(self.stacks)-1)
    

    def popAtStack(self, index: int) -> int:
        if 0<=index<len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.availIndexes,index)
            return self.stacks[index].pop()
        return -1
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stack = []
        self.available_to_push = []   # min heap to store the idx of available-to-push stack

    def push(self, val: int) -> None:       # O(logn)
        # step 1: pop out all the left stacks that are not avaliable to push, 
        # so that after the while loop, we will know the leftmost stack that is available to push
        while len(self.available_to_push) > 0 and self.available_to_push[0] < len(self.stack) and len(self.stack[self.available_to_push[0]]) == self.capacity:
            heappop(self.available_to_push)
            
        # if the q is empty, meaning there are no more available stacks
        if len(self.available_to_push) == 0:        
            heappush(self.available_to_push, len(self.stack))
        if self.available_to_push[0] == len(self.stack):
            self.stack.append([])
            
        # finally, we can push our val into the leftmost available stack
        self.stack[self.available_to_push[0]].append(val)

    def pop(self) -> int:       # O(1)
        # step 1: pop out all the empty stacks on the right, cuz they are not available to pop
        while len(self.stack) > 0 and len(self.stack[-1]) == 0:
            self.stack.pop()
            
        return self.popAtStack(len(self.stack) - 1)

    def popAtStack(self, index: int) -> int:        # O(logn)
        # check if it is available to pop
        if 0 <= index < len(self.stack) and len(self.stack[index]) > 0:
            heappush(self.available_to_push, index)     # add this index to the available-to-push heap
            return self.stack[index].pop()
        return -1
        


# 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)


import heapq

class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.capacity = capacity
        self.toPush = []

    def push(self, val: int) -> None:
        if not self.stacks:
            self.stacks.append([val])
        else:
            if self.toPush and self.toPush[0] < len(self.stacks):
                i = heapq.heappop(self.toPush)
                self.stacks[i].append(val)
            else:
                self.stacks[-1].append(val)
                
        if len(self.stacks[-1]) == self.capacity:
            self.stacks.append([])

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop() 
            # self.toPush = min(self.toPush, len(self.stacks)-1)
        
        if not self.stacks:
            return -1
        
        return self.stacks[-1].pop()

    def popAtStack(self, index: int) -> int:
        if index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.toPush, index)
            return self.stacks[index].pop()
        return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.rightheap=[]
        self.leftheap=[]
        heapq.heappush(self.leftheap,0)
        self.hashmap=defaultdict(list)
        self.capacity=capacity
        self.ind=0

    def push(self, val: int) -> None:
        slot=self.leftheap[0]
        if len(self.hashmap[slot])==0:
            heapq.heappush(self.rightheap,-slot)
        self.hashmap[slot].append(val)
        if len(self.hashmap[slot])==self.capacity:
            heapq.heappop(self.leftheap)
            
        if len(self.leftheap)==0:
            self.ind+=1
            heapq.heappush(self.leftheap,self.ind)
            
       

    def pop(self) -> int:
        if not self.rightheap:
            return -1
        while(len(self.hashmap[-self.rightheap[0]])==0):
              heapq.heappop(self.rightheap)
        slot=-heapq.heappop(self.rightheap)
        value=self.hashmap[slot].pop()
        if len(self.hashmap[slot])!=0:
            heapq.heappush(self.rightheap,-slot)
        else:
            self.ind=slot-1
        heapq.heappush(self.leftheap,slot)
        
        return value
        

    def popAtStack(self, index: int) -> int:
        if not self.hashmap[index]:
            return -1
        else:
            value=self.hashmap[index].pop()
            if len(self.hashmap[index])+1==self.capacity:
                heapq.heappush(self.leftheap,index)
            return value     
        


# 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)


import heapq

class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.capacity = capacity
        self.toPush = []

    def push(self, val: int) -> None:
        if not self.stacks:
            self.stacks.append([val])
        else:
            if self.toPush and self.toPush[0] < len(self.stacks):
                i = heapq.heappop(self.toPush)
                self.stacks[i].append(val)
            else:
                self.stacks[-1].append(val)
                
        if len(self.stacks[-1]) == self.capacity:
            self.stacks.append([])


    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop() 
            # self.toPush = min(self.toPush, len(self.stacks)-1)
        
        if not self.stacks:
            return -1
        
        return self.stacks[-1].pop()

    def popAtStack(self, index: int) -> int:
        if index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.toPush, index)
            return self.stacks[index].pop()
        return -1


# 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)


import heapq

class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.leftmost = []
        self.K = capacity

    def push(self, val: int) -> None:
        if len(self.leftmost) == 0:
            if self.K != 1:
                self.leftmost.append(len(self.stacks))
            self.stacks.append([val])
        else:
            ind = self.leftmost[0]
            if ind >= len(self.stacks):
                self.stacks.append([])
            self.stacks[ind].append(val)
            if len(self.stacks[ind]) == self.K:
                heapq.heappop(self.leftmost)
            
    def pop(self) -> int:
        if len(self.stacks) == 0:
            return -1
            
        while len(self.stacks[-1]) == 0:
            self.stacks.pop()
            if len(self.stacks) == 0:
                return -1
            
        if len(self.stacks[-1]) == self.K:
            heapq.heappush(self.leftmost,len(self.stacks)-1)
            
        return self.stacks[-1].pop()

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks):
            return -1
        else:
            stack = self.stacks[index]
            if len(stack) == 0:
                return -1
            
            if len(stack) == self.K:
                heapq.heappush(self.leftmost,index)
            
            return stack.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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks = list()
        self.RMNE = -1
        self.LMNF = -1

    def push(self, val: int) -> None:
        if(self.LMNF <0 or self.LMNF >= len(self.stacks)):
            self.stacks.append([val])
            self.RMNE = len(self.stacks)
            if(self.capacity > 1):
                self.LMNF = len(self.stacks)-1
            #if(self.LMNF < 0):self.LMNF = len(self.stacks)
        else:
            if(len(self.stacks[self.LMNF]) == self.capacity):
                self.LMNF += 1
                self.push(val)
                return
            self.stacks[self.LMNF].append(val)
            if(self.RMNE < self.LMNF):
                self.RMNE = self.LMNF        
                
            if(len(self.stacks[self.LMNF]) == self.capacity):
                self.LMNF += 1
                
                
    def pop(self) -> int:
        
        if(self.RMNE >= len(self.stacks)):
            self.RMNE = len(self.stacks) - 1
        while(self.RMNE>=0 and not self.stacks[self.RMNE]):
            self.RMNE -= 1
            self.stacks.pop()      
        if(self.RMNE <0):
            return -1
        val = self.stacks[self.RMNE].pop()
        if(self.LMNF > self.RMNE):
            self.LMNF = self.RMNE
        return val        

    def popAtStack(self, index: int) -> int:
        if(index >= len(self.stacks)):
            return -1;
        if(len(self.stacks[index])==0):
            return -1;
        val = self.stacks[index].pop()
        if(self.LMNF > index or self.LMNF<0):
            self.LMNF = index        
        return val
        
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks = list()
        self.RMNE = -1
        self.LMNF = -1

    def push(self, val: int) -> None:
        if(self.LMNF <0 or self.LMNF >= len(self.stacks)):
            self.stacks.append([val])
            self.RMNE = len(self.stacks)
            if(self.capacity > 1):
                self.LMNF = len(self.stacks)-1
        else:
            if(len(self.stacks[self.LMNF]) == self.capacity):
                self.LMNF += 1
                self.push(val)
                return
            self.stacks[self.LMNF].append(val)
            if(self.RMNE < self.LMNF):
                self.RMNE = self.LMNF        
                
            if(len(self.stacks[self.LMNF]) == self.capacity):
                self.LMNF += 1
                
                
    def pop(self) -> int:
        
        if(self.RMNE >= len(self.stacks)):
            self.RMNE = len(self.stacks) - 1
        while(self.RMNE>=0 and not self.stacks[self.RMNE]):
            self.RMNE -= 1
            self.stacks.pop()      
        if(self.RMNE <0):
            return -1
        val = self.stacks[self.RMNE].pop()
        if(self.LMNF > self.RMNE):
            self.LMNF = self.RMNE
        return val        

    def popAtStack(self, index: int) -> int:
        if(index >= len(self.stacks)):
            return -1;
        if(len(self.stacks[index])==0):
            return -1;
        val = self.stacks[index].pop()
        if(self.LMNF > index or self.LMNF<0):
            self.LMNF = index        
        return val
        
        


# 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)


class DinnerPlates:

    def __init__(self, capacity):
        
        self.stacks=[]
        self.stack=[]
        self.size=capacity
        self.left=0
        self.right=0

    def push(self, val):
       
        #when stack is initially empty
        if not self.stacks:            
            self.stack.append(val)
            self.stacks.append(self.stack)
            self.left=0
                           
        else:   
            #find the leftmost stack with size less than capacity to append item
            while self.left<len(self.stacks) and len(self.stacks[self.left])==self.size:
                self.left+=1
            if self.left==len(self.stacks):
                self.stacks.append([])
                self.stacks[self.left].append(val)
            else:
                self.stacks[self.left].append(val)                
                        
            self.right=len(self.stacks)-1

    def pop(self):
      
        if not self.stacks:
            return -1
        
        #find the rightmost non empty stack
        if not self.stacks[self.right]:
            while not self.stacks[self.right] and len(self.stacks)-1>=self.right:                
                self.stacks.pop(self.right)
                self.right-=1
                
        item=self.stacks[self.right].pop() 
        
        #if stack gets empty after pop item, move the pointer for rightmost non empty stack
        if not self.stacks[self.right]:
            self.stacks.pop(self.right)
            self.right-=1           
         
        return item                        
        
    def popAtStack(self, index):
       
        if len(self.stacks)-1<index:
            return -1
        if not self.stacks[index]:
            return -1
        
        #before popping item from stack at index, update the pointer for leftmost stack with capacity
        if self.stacks[index]:
            if self.left>index:
                self.left=index
        return self.stacks[index].pop()

class DinnerPlates:
    #Use heap to store index of available stack
    def __init__(self, capacity: int):
        self.cap = capacity
        self.stacks = []
        self.heap = []

    def push(self, val: int) -> None:
        if not self.heap:
            self.stacks.append([val])
            if len(self.stacks[-1]) < self.cap:
                heapq.heappush(self.heap, len(self.stacks)-1)
        else:
            i = heapq.heappop(self.heap)
            while self.heap and i < len(self.stacks) and len(self.stacks[i]) >= self.cap: 
                i = heapq.heappop(self.heap)
            if i >= len(self.stacks):
                self.stacks.append([val])
            
            else:
                self.stacks[i].append(val)
            if len(self.stacks[i]) < self.cap:
                heapq.heappush(self.heap, i)
            

    def pop(self) -> int:
        return self.popAtStack(len(self.stacks)-1)

    def popAtStack(self, index: int) -> int:
        if self.stacks == []: return -1
        if index < len(self.stacks) and self.stacks[index] == []: return -1
        
        if index < len(self.stacks) and self.stacks[index] != []: 
            item = self.stacks[index].pop()
            if self.stacks[index] == [] and index == len(self.stacks) - 1:
                while self.stacks and self.stacks[-1] == []:
                    self.stacks.pop()
            else:
                heapq.heappush(self.heap, index)
                
            return item
        return -1

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.slots = []
        self.capacity = capacity
        self.plates = []
        self.end = -1
        

    def push(self, val: int) -> None:
        if len(self.slots) == 0:
            self.plates.append([])
            self.plates[-1].append(val)
            self.slots += [len(self.plates) - 1] * (self.capacity - 1)
        else:
            self.plates[heappop(self.slots)].append(val)
            
        self.end = max(self.end, len(self.plates) - 1)
        

    def pop(self) -> int:
        if self.end < 0:
            return -1
        
        return self.popAtStack(self.end)
        

    def popAtStack(self, index: int) -> int:
        if index >= len(self.plates) or len(self.plates[index]) == 0:
            return -1
        
        ret = self.plates[index].pop()
        heappush(self.slots, index)
        
        while self.end >= 0 and len(self.plates[self.end]) == 0:
            self.end -= 1
            
        return ret
        

# 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)


from collections import deque as dq
import bisect as bs
class DinnerPlates:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.nFull = []
        self.cur = []

    def push(self, val: int) -> None:
        # print(\"push\", val, self.cur, self.nFull)
        if self.nFull:
            self.cur[self.nFull[0]].append(val)
            if len(self.cur[self.nFull[0]]) == self.cap:
                self.nFull.pop(0)
        else:
            self.cur.append([val])
            if len(self.cur[-1]) < self.cap:
                self.nFull.append(len(self.cur)-1)

    def pop(self) -> int:
        # print(\"pop\", self.cur, self.nFull)
        if not self.cur:
            return -1
        tmp = self.cur[-1].pop()
        if len(self.cur[-1]) == self.cap - 1:
            if self.cur[-1]:
                self.nFull.append(len(self.cur) - 1)
            else:
                self.cur.pop()
        while self.cur and not self.cur[-1]:
            self.cur.pop()
            self.nFull.pop()
        return tmp
        

    def popAtStack(self, index: int) -> int:   
        # print(\"popAt\", index, self.cur, self.nFull)
        if index >= len(self.cur):
            return -1
        if self.cur[index]:
            tmp = self.cur[index].pop()
            if len(self.cur[index]) == self.cap - 1:
                if self.cur[index]:
                    bs.insort(self.nFull, index)
                else:
                    if index == len(self.cur) - 1:
                        self.cur.pop()
                        while self.cur and not self.cur[-1]:
                            self.cur.pop()
                            self.nFull.pop()
                    else:
                        bs.insort(self.nFull, index)
            return tmp
        else:
            return -1


# 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)


class DinnerPlates(object):

    def __init__(self, capacity):
        \"\"\"
        :type capacity: int
        \"\"\"
        self.stacks = []
        self.cap = capacity
        self.not_full = [] #to push min heap
        self.not_empty = [] #to pop

    def push(self, val):
        \"\"\"
        :type val: int
        :rtype: None
        \"\"\"
        #print(\"push\")
        if self.not_full:
            index = self.not_full[0]
            self.stacks[index].append(val)
            if len(self.stacks[index]) == self.cap:
                heapq.heappop(self.not_full)
                
        else:
            index = len(self.stacks)
            if self.cap > 1: #here
                heapq.heappush(self.not_full, index)
            heapq.heappush(self.not_empty, -index)
            self.stacks += [[val]]
            
    def pop(self):
        \"\"\"
        :rtype: int
        \"\"\"

        #print(\"pop\")
        while self.not_empty and not self.stacks[-self.not_empty[0]]:
            heapq.heappop(self.not_empty)
            self.stacks.pop() #here
            
        if self.not_empty:
            index = -self.not_empty[0]
            val = self.stacks[index].pop()
            if not self.stacks[index]:
                heapq.heappop(self.not_empty)
                self.stacks.pop()
                
            return val
        
        return -1
        
        
        

    def popAtStack(self, index):
        \"\"\"
        :type index: int
        :rtype: int
        \"\"\"
        #print(\"popAt\")
        if index >= 0 and index < len(self.stacks) and self.stacks[index]:
            if len(self.stacks[index]) == self.cap and index != len(self.stacks) - 1:
                heapq.heappush(self.not_full, index)  
            return self.stacks[index].pop()
        
        return -1

class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks = list()
        self.RMNE = -1
        self.LMNF = -1

    def push(self, val: int) -> None:
        if(self.LMNF <0 or self.LMNF >= len(self.stacks)):
            self.stacks.append([val])
            self.RMNE = len(self.stacks)
            if(self.capacity > 1):
                self.LMNF = len(self.stacks)-1
            if(self.LMNF < 0):
                self.LMNF = len(self.stacks)
        else:
            if(len(self.stacks[self.LMNF]) == self.capacity):
                self.LMNF += 1
                self.push(val)
                return
            self.stacks[self.LMNF].append(val)
            if(self.RMNE < self.LMNF):
                self.RMNE = self.LMNF        
                
            if(len(self.stacks[self.LMNF]) == self.capacity):
                self.LMNF += 1
                
                
    def pop(self) -> int:
        
        if(self.RMNE >= len(self.stacks)):
            self.RMNE = len(self.stacks) - 1
        while(self.RMNE>=0 and not self.stacks[self.RMNE]):
            self.RMNE -= 1
            self.stacks.pop()      
        if(self.RMNE <0):
            return -1
        val = self.stacks[self.RMNE].pop()
        if(self.LMNF > self.RMNE):
            self.LMNF = self.RMNE
        return val        

    def popAtStack(self, index: int) -> int:
        if(index >= len(self.stacks)):
            return -1;
        if(len(self.stacks[index])==0):
            return -1;
        val = self.stacks[index].pop()
        if(self.LMNF > index or self.LMNF<0):
            self.LMNF = index        
        return val
        
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity, self.stacks = capacity, [[]]
        self.left = 0
        self.right = 0

    def push(self, val: int) -> None:
        while self.left < len(self.stacks) and len(self.stacks[self.left]) == self.capacity:
            self.left += 1
        if self.left == len(self.stacks):
            self.stacks.append([val])
        else:
            self.stacks[self.left].append(val)
        
        if self.left >= self.right:
            self.right = self.left
    def pop(self) -> int:
        while self.right > 0  and len(self.stacks[self.right]) == 0:
            self.stacks.pop()
            self.right -= 1
        if self.right < self.left:
            self.left = self.right
        
        if len(self.stacks[self.right]) == 0:
            return -1
        
        
        return self.stacks[self.right].pop()
    

    def popAtStack(self, index: int) -> int:
        if index > len(self.stacks) or not self.stacks[index]:
            return -1
        if index < self.left:
            self.left = index
        return self.stacks[index].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)


from collections import deque
import heapq

class DinnerPlates:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacklist = []
        self.minh = []
        # heapq.heapify(self.minh)

    def push(self, val: int) -> None:
        while len(self.minh) > 0:
            lms = heapq.heappop(self.minh)
            if len(self.stacklist) - 1 < lms:
                continue
            else:
                self.stacklist[lms].append(val)
                break
        else:
            if len(self.stacklist) == 0 or len(self.stacklist[-1]) >= self.capacity:
                self.stacklist.append(deque())
            self.stacklist[-1].append(val)

    def pop(self) -> int:
        if len(self.stacklist) == 0:
            return -1

        while len(self.stacklist[-1]) == 0:
            del self.stacklist[-1]

        if len(self.stacklist) > 0:
            res = self.stacklist[-1].pop()
        else:
            res = -1

        if len(self.stacklist[-1]) == 0:
            del self.stacklist[-1]

        return res

    def popAtStack(self, index: int) -> int:
        if len(self.stacklist) - 1 < index or len(self.stacklist[index]) == 0:
            return -1
        else:
            res = self.stacklist[index].pop()
            heapq.heappush(self.minh, index)
            return res


# 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)



class DinnerPlates(object):
    
  def __init__(self, capacity):
    self.capacity, self.stacks = capacity, [[]]
    self.left, self.right = 0, 0

  def push(self, val):
    while self.left < len(self.stacks) and len(self.stacks[self.left]) == self.capacity:
      self.left += 1 # find the leftmost stack with space
    if self.left == len(self.stacks):
      self.stacks += [],  # all our stacks are full, add a new one on the right
    self.stacks[self.left] += val,  
    if self.left > self.right:
      self.right = self.left # update right pointer if needed

  def pop(self):
    while self.right > 0 and not len(self.stacks[self.right]):
      self.stacks.pop() # clear up any empty stacks on the right
      self.right -= 1
    if self.right < self.left:
      self.left = self.right  # update left pointer if needed
    return -1 if not len(self.stacks[self.right]) else self.stacks[self.right].pop()

  def popAtStack(self, index):
    if index > len(self.stacks) or not len(self.stacks[index]):
      return -1
    if index < self.left:
      self.left = index # we have an empty space even more left than before
    return self.stacks[index].pop()

class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.s = []
        self.q = []
            
    def push(self, val: int) -> None:
        if not self.q or self.q[0] > len(self.s)-1:
            self.s.append([val])
            self.q = []
            if self.c > 1:
                heapq.heappush(self.q, len(self.s)-1)
        else:
            temp = heapq.heappop(self.q)
            self.s[temp].append(val)
            if len(self.s[temp]) < self.c:
                heapq.heappush(self.q, temp)
        
    def pop(self) -> int:
        while self.s and not self.s[-1]:
            self.s.pop()
            
        if not self.s:
            return -1
        
        if len(self.s[-1]) == self.c:
            heapq.heappush(self.q, len(self.s)-1)
        return self.s[-1].pop()

    def popAtStack(self, index: int) -> int:
        if index < 0 or index > len(self.s)-1:
            return -1
        
        if len(self.s[index]) == self.c:
            heapq.heappush(self.q, index)
            
        return self.s[index].pop() if self.s[index] else -1


# 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)


import heapq
class DinnerPlates:
    def __init__(self, capacity: int):
        self.cache = []
        self.capacity = capacity
        self.available_pos = []

    def push(self, val: int) -> None:
        if len(self.available_pos) == 0:
            self.cache.append([])
            heapq.heappush(self.available_pos, len(self.cache) - 1)
        min_idx = self.available_pos[0]
        if min_idx >= len(self.cache):
            needed = min_idx + 1 - len(self.cache)
            for _ in range(needed):
                self.cache.append([])
        self.cache[min_idx].append(val)
        if len(self.cache[min_idx]) == self.capacity:
            heapq.heappop(self.available_pos)

    def pop(self) -> int:
        while len(self.cache) > 0 and len(self.cache[-1]) == 0:
            self.cache.pop()
        if len(self.cache) == 0: return -1
        
        val = self.cache[-1].pop()
        # if len(self.cache[-1]) == 0: 
        #     self.cache.pop()
        if len(self.cache[-1]) == self.capacity - 1:
            heapq.heappush(self.available_pos, len(self.cache) - 1)
        return val

    def popAtStack(self, index: int) -> int:
        if index >= len(self.cache) or len(self.cache[index]) == 0: return -1
        val = self.cache[index].pop()
        if len(self.cache[index]) == self.capacity - 1:
            heapq.heappush(self.available_pos, index)
        return val


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.data = [[]]
        self.cap = capacity
        self.i = 0

    def push(self, val: int) -> None:
        self.data[self.i].append(val)
        while self.i < len(self.data) and len(self.data[self.i]) == self.cap:
            self.i += 1
        if self.i == len(self.data):
            self.data.append([])

    def pop(self) -> int:
        while self.data and not self.data[-1]:
            self.data.pop()
        
        if self.data:
            if len(self.data) <= self.i:
                self.i -= 1
            return self.data[-1].pop()
        return -1

    def popAtStack(self, index: int) -> int:
        if index < len(self.data) and self.data[index]:
            if index < self.i:
                self.i = index
            return self.data[index].pop()
        return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.capacity = capacity
        self.toPush = None

    def push(self, val: int) -> None:
        if not self.stacks:
            self.stacks.append([val])
            self.toPush = 0

        else:
            self.stacks[self.toPush].append(val)
                
        if len(self.stacks[-1]) == self.capacity:
            self.stacks.append([])
            
        while len(self.stacks[self.toPush]) == self.capacity:
            self.toPush += 1

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop() 
            self.toPush = min(self.toPush, len(self.stacks)-1)
        
        if not self.stacks:
            return -1
        
        return self.stacks[-1].pop()

    def popAtStack(self, index: int) -> int:
        if index < len(self.stacks) and self.stacks[index]:
            self.toPush = min(self.toPush, index)
            return self.stacks[index].pop()
        return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.q = [] # record the available stack, will use heap to quickly find the smallest available stack
        # if you are Java or C++ users, tree map is another good option.
        self.stacks = [] # record values of all stack of plates, its last nonempty stack are the rightmost position

    def push(self, val: int) -> None:
        # To push, we need to find the leftmost available position
        # first, let's remove any stacks on the left that are full
        # 1) self.q: if there is still available stack to insert plate
        # 2) self.q[0] < len(self.stacks): the leftmost available index self.q[0] is smaller than the current size of the stacks
        # 3) len(self.stacks[self.q[0]]) == self.c: the stack has reached full capacity
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            # we remove the filled stack from the queue of available stacks
            heapq.heappop(self.q)

        # now we reach the leftmost available stack to insert

        # if the q is empty, meaning there are no more available stacks
        if not self.q:
            # open up a new stack to insert
            heapq.heappush(self.q, len(self.stacks))

        # for the newly added stack, add a new stack to self.stacks accordingly
        if self.q[0] == len(self.stacks):
            self.stacks.append([])

        # append the value to the leftmost available stack
        self.stacks[self.q[0]].append(val)

    def pop(self) -> int:
        # To pop, we need to find the rightmost nonempty stack
        # 1) stacks is not empty (self.stacks) and
        # 2) the last stack is empty
        while self.stacks and not self.stacks[-1]:
            # we throw away the last empty stack, because we can't pop from it
            self.stacks.pop()

        # now we reach the rightmost nonempty stack

        # we pop the plate from the last nonempty stack of self.stacks by using popAtStack function
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index: int) -> int:
        # To pop from an stack of given index, we need to make sure that it is not empty
        # 1) the index for inserting is valid and，
        # 2) the stack of interest is not empty
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            # we add the index into the available stack
            heapq.heappush(self.q, index)
            # take the top plate, pop it and return its value
            return self.stacks[index].pop()

        # otherwise, return -1 because we can't pop any plate
        return -1


# 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)


# 1172. Dinner Plate Stacks

from heapq import *

class DinnerPlates:
    def __repr__ (self):
        return f'DP ({self.stacks}, {self.nonfull})'
    
    def __init__ (self, capacity):
        self.cap = capacity
        self.stacks = []
        self.nonfull = [] # heap

    def push (self, val):
        # look in self.nonfull first
        while self.nonfull:
            first = self.nonfull [0]
            if first < len (self.stacks) and len (self.stacks[first]) < self.cap:
                self.stacks[first].append (val)
                if len (self.stacks[first]) == self.cap:
                    # no longer nonfull
                    heappop (self.nonfull)
                return
            else:
                heappop (self.nonfull)
        # not found yet
        new_stack = len (self.stacks)
        self.stacks.append ([val])
        if len (self.stacks[new_stack]) < self.cap:
            heappush (self.nonfull, new_stack)

    def pop (self):
        while self.stacks:
            if not self.stacks[-1]:
                self.stacks.pop ()
            else:
                ans = self.stacks[-1].pop ()
                popped_stack = len (self.stacks) - 1
                if not self.stacks[-1]:
                    self.stacks.pop ()
                elif len (self.stacks[-1]) == self.cap - 1:
                    heappush (self.nonfull, popped_stack)
                return ans
        return -1

    def popAtStack (self, index):
        if index >= len (self.stacks):
            return -1
        elif not self.stacks[index]:
            return -1
        else:
            ans = self.stacks[index].pop ()
            if len (self.stacks[index]) == self.cap - 1:
                heappush (self.nonfull, index)
            return ans

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.stack = []
        self.cap = capacity
        self.left = 0
        self.right = 0
        

    def push(self, val: int) -> None:
        if not self.stacks:
            self.stack.append(val)
            self.stacks.append(self.stack)
        else:
            while self.left < len(self.stacks) and len(self.stacks[self.left]) == self.cap:
                self.left += 1
            if self.left == len(self.stacks):
                self.stacks.append([])
                self.stacks[self.left].append(val)
                self.right = len(self.stacks) - 1
            else:
                self.stacks[self.left].append(val)
            
                

    def pop(self) -> int:
        if not self.stacks:
            return -1
        if not self.stacks[self.right]:
            while not self.stacks[self.right]:
                self.stacks.pop()
                self.right -= 1
                
        item = self.stacks[self.right].pop()
        
        if not self.stacks[self.right]:
            self.stacks.pop()
            self.right -= 1
        return item
                
        

    def popAtStack(self, index: int) -> int:
        if index > len(self.stacks) - 1:
            return -1
        if not self.stacks[index]:
            return -1
        if self.stacks[index]:
            if self.left > index:
                self.left = index
            item = self.stacks[index].pop()
            return item


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks = list()
        self.heapnonfull = list()
        self.heapnonempty = list()
        


    def push(self, val: int) -> None:
        if(len(self.heapnonfull)==0):
            newlist = list()
            newlist.append(val)
            self.stacks.append(newlist)
            index = len(self.stacks) - 1
            if(self.capacity > 1):
                heappush(self.heapnonfull, index)
            heappush(self.heapnonempty, 0-index)
        else:
            index = self.heapnonfull[0]
            self.stacks[index].append(val)
            if(len(self.stacks[index]) == self.capacity):
                heappop(self.heapnonfull)

    def pop(self) -> int:

        while(len(self.heapnonempty) > 0 and len(self.stacks[0- self.heapnonempty[0]])==0):
            heappop(self.heapnonempty)
            self.stacks.pop()

        if(len(self.heapnonempty)==0):
            return -1
        index = 0 - self.heapnonempty[0]
        val = self.stacks[index].pop()
        if(len(self.stacks[index])==0):
            heappop(self.heapnonempty) 
            self.stacks.pop()
        else:
            if(len(self.stacks[index]) < self.capacity):                  
                heappush(self.heapnonfull, index)
        return val

    def popAtStack(self, index: int) -> int:
        if(index >= len(self.stacks)):
            return -1;
                    
        curlen = len(self.stacks[index])
        if(curlen==0):
            return -1
                     
        #if(curlen==1):
        #    self.heapnonempty.remove(0-index)
        #    heapify(self.heapnonempty)
            
        if(curlen-1 < self.capacity and curlen==self.capacity and index != len(self.stacks) - 1):                     
            heappush(self.heapnonfull, index)                    
                    
        return self.stacks[index].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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stack = [[]]
        self.cap = capacity
        self.heap = [0]
        
    def push(self, val: int) -> None:
        while self.heap and self.heap[0]<len(self.stack) and len(self.stack[self.heap[0]])==self.cap:
            heapq.heappop(self.heap)
            
        if not self.heap:
            heapq.heappush(self.heap, len(self.stack))
        if self.heap[0]>=len(self.stack):
            self.stack.append([])
        self.stack[self.heap[0]].append(val)
        
    def pop(self) -> int:
        while self.stack and not self.stack[-1]:
            self.stack.pop()
        if not self.stack:
            return -1
        res = self.stack[-1].pop()
        heapq.heappush(self.heap, len(self.stack)-1)
        return res

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stack) or not self.stack[index]:
            return -1
        heapq.heappush(self.heap, index)
        return self.stack[index].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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.pq = []
        self.sta = []
        

    def push(self, val: int) -> None:
        def push_at(index, val):
            if (index < 0 or index >= len(self.sta) or len(self.sta[index]) == self.cap):
                self.sta.append([val])
            else:
                self.sta[index].append(val)
        
        insert_idx = heapq.heappop(self.pq) if self.pq else len(self.sta)-1
        push_at(insert_idx, val)

    def pop(self) -> int:
        while (self.sta and (not self.sta[-1])):
            self.sta.pop()
            
        return self.popAtStack(len(self.sta)-1)

    def popAtStack(self, index: int) -> int:
        if (0 <= index < len(self.sta) and self.sta[index]):
            heapq.heappush(self.pq,index)
            return self.sta[index].pop()
        return -1



# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.stacks = []
        self.idx = []

    def push(self, val: int) -> None:
        if self.idx and 0 <= -self.idx[-1] < len(self.stacks):
            i = -self.idx[-1]
            st = self.stacks[i]
            st.append(val)
            if len(st) == self.cap:
                self.idx.pop()
        else:
            self.idx.clear()
            self.stacks.append([val])
            if self.cap > 1:
                self.idx.append(-len(self.stacks) + 1)                        
        
    def pop(self) -> int:
        if not self.stacks:
            return -1
        st = self.stacks[-1]
        val = st.pop()
        if len(st) == self.cap - 1:
            bisect.insort(self.idx, -len(self.stacks) + 1)
        self._clean()
        return val

    def popAtStack(self, index: int) -> int:
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            st = self.stacks[index]
            val = st.pop()
            if len(st) == self.cap - 1:
                bisect.insort(self.idx, -index)
            self._clean()
            return val
        return -1
    
    def _clean(self):
        while self.stacks and not self.stacks[-1]:
            self.stacks.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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.q = []
        self.stacks = []

    def push(self, val: int) -> None:
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            heapq.heappop(self.q)
        if not self.q:
            heapq.heappush(self.q,len(self.stacks))
        if self.q[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.q[0]].append(val)

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index: int) -> int:
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.q,index)
            return self.stacks[index].pop()
        return -1

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.q = []
        self.stacks = []

    def push(self, val: int) -> None:
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            heapq.heappop(self.q)
        if not self.q:
            heapq.heappush(self.q,len(self.stacks))
        if self.q[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.q[0]].append(val)

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index: int) -> int:
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.q,index)
            return self.stacks[index].pop()
        return -1


# 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)


import heapq
class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.vacancy = []
        self.stacks = []
        self.maxidx = -1

    def push(self, val: int) -> None:
        if self.vacancy:
            pos = self.vacancy[0]
            self.stacks[pos].append(val)
            if len(self.stacks[pos]) == self.capacity:
                heapq.heappop(self.vacancy)
        else:
            pos = len(self.stacks)
            self.stacks.append([])
            self.stacks[pos].append(val)
            if self.capacity > 1:
                heapq.heappush(self.vacancy, pos)
        self.maxidx = max(self.maxidx, pos)


    def pop(self) -> int:
        rangemax = self.maxidx
        for i in range(rangemax, -1, -1):
            if self.stacks[i] != []:
                self.maxidx = i
                x = self.stacks[i].pop()
                if len(self.stacks[i]) == self.capacity - 1:
                    heapq.heappush(self.vacancy, i)
                return x
        else:
            return -1

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks) or self.stacks[index] == []:
            return -1
        if len(self.stacks[index]) == self.capacity:
            heapq.heappush(self.vacancy, index)
            return self.stacks[index].pop()
        else:
            return self.stacks[index].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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.q = []
        self.stacks = []

    def push(self, val: int) -> None:
        # 1) self.q: is there is available leftmost index
        # 2) is leftmost index less than current size of stacks
        # 3) is leftmost index full
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            heappop(self.q)
        
        if not self.q:
            heappush(self.q, len(self.stacks))
        if self.q[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.q[0]].append(val)
            

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        if len(self.stacks) == 0:
            return -1
        return self.popAtStack(len(self.stacks)-1)

    def popAtStack(self, index: int) -> int:
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            heappush(self.q, index)
            return self.stacks[index].pop()
        return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks = []
        self.available = []
        
    def push(self, val: int) -> None:
        if not self.available:
            self.stacks.append([])
            self.available.append(len(self.stacks) - 1)
        slot = self.available[0]
        self.stacks[slot].append(val)
        if len(self.stacks[slot]) == self.capacity:
            heapq.heappop(self.available)
            self.remove_empty_stacks()
    
    def remove_empty_stacks(self):
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        while self.available and self.available[0] >= len(self.stacks):
            heapq.heappop(self.available)
        
    def pop(self) -> int:
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index: int) -> int:
        if index < 0 or index >= len(self.stacks) or not self.stacks[index]:
            return -1
        result = self.stacks[index].pop()
        if len(self.stacks[index]) == self.capacity - 1:
            heapq.heappush(self.available, index)
        self.remove_empty_stacks()
        return result


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.h = [0]
        self.counter = 0
        self.stacks = [[]]
        self.cap = capacity
        

    def push(self, val: int) -> None:
        if self.h:
            i = heapq.heappop(self.h)
            if i >=len(self.stacks):
                self.push(val)
            else:
                self.stacks[i].append(val)
            if len(self.stacks[i]) <self.cap:
                heapq.heappush(self.h, i)

        else:
            self.stacks.append([val])
            if len(self.stacks[-1]) <self.cap:
                heapq.heappush(self.h, len(self.stacks)-1)
        

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        if self.stacks:
            return self.stacks[-1].pop()
        return -1
        

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks):
            return -1
        if len(self.stacks[index]) == self.cap:
            heapq.heappush(self.h, index)
        if self.stacks[index]:
            return self.stacks[index].pop()
        return -1
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.heap = []
        self.stacks = []

    def push(self, val: int) -> None:
        while self.heap and self.heap[0] < len(self.stacks) and len(self.stacks[self.heap[0]]) == self.capacity:
            heapq.heappop(self.heap)
        
        if not self.heap:
            heapq.heappush(self.heap, len(self.stacks))
        if self.heap[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.heap[0]].append(val)
        
    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index: int) -> int:
        if index >= 0 and index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.heap, index)
            return self.stacks[index].pop()
        return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.stacks = []
        self.pq = []

    def push(self, val: int) -> None:
        
        while self.pq and len(self.stacks) > self.pq[0] and len(self.stacks[self.pq[0]]) == self.cap:
            heapq.heappop(self.pq)
        if not self.pq:
            heapq.heappush(self.pq, len(self.stacks))
        if self.pq[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.pq[0]].append(val)

      
    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        if not self.stacks:
            return -1
        return self.popAtStack(len(self.stacks) -  1)

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks) or not self.stacks[index]:
            return -1
        val = self.stacks[index].pop()
        heapq.heappush(self.pq, index)
        return val


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stack_list = []
        self.available_stacks = []

    def push(self, val: int) -> None:
        while self.available_stacks and self.available_stacks[0] >= len(self.stack_list):
            heapq.heappop(self.available_stacks)
        if not self.available_stacks:
            self.stack_list.append([])
            self.available_stacks.append(len(self.stack_list) - 1)
        first_available_stack = self.available_stacks[0]
        self.stack_list[first_available_stack].append(val)
        if len(self.stack_list[first_available_stack]) == self.capacity:
            heapq.heappop(self.available_stacks)

    def pop(self) -> int:
        while self.stack_list and not self.stack_list[-1]:
            self.stack_list.pop()
        return self.popAtStack(len(self.stack_list) - 1)
        
        
    def popAtStack(self, index: int) -> int:
        if index < 0 or index > len(self.stack_list) - 1 or not self.stack_list[index]:
            return -1
        if len(self.stack_list[index]) == self.capacity:
            heapq.heappush(self.available_stacks, index)
        result = self.stack_list[index].pop()
        return result


# 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)


import heapq
class DinnerPlates:
    def __init__(self, capacity: int):
        # record values of all stack of plates, its last nonempty stack are the rightmost position
        self.stk = []
        self.c = capacity
        # record the available stack, will use heap to quickly find the smallest available stack
        self.pq = []

    def push(self, val: int) -> None:
        # Time: O(logN)
        # To push, we need to find the leftmost available position. first, let's remove any stacks on the left that are full
        while self.pq and self.pq[0] < len(self.stk) and len(self.stk[self.pq[0]]) == self.c:
            heapq.heappop(self.pq)
        
        # if the q is empty, meaning there are no more available stacks
        if len(self.pq) == 0:
            heapq.heappush(self.pq, len(self.stk))
        
        # for the newly added stack, add a new stack to self.stacks accordingly
        # Key: this new idx NOT NECESSARY added by above \"if\", it MIGHT already in self.pq
        if self.pq[0] == len(self.stk):
            self.stk.append([])
        
        # append the value to the leftmost available stack
        self.stk[self.pq[0]].append(val)

    def pop(self) -> int:
        # Time: amortized O(1)
        # To pop, we need to find the rightmost nonempty stack
        # 1) stacks is not empty (self.stacks) and
        # 2) the last stack is empty
        while len(self.stk) > 0 and len(self.stk[-1]) == 0:
            self.stk.pop()
         
        return self.popAtStack(len(self.stk) - 1)

    def popAtStack(self, index: int) -> int:
        # Time: O(logN)
        # To pop from an stack of given index, we need to make sure that it is not empty
        # 1) the index for inserting is valid and，
        # 2) the stack of interest is not empty
        if 0 <= index < len(self.stk) and len(self.stk[index]):
            # we add the index into the available stack
            # Also can add index ONLY when length changes from capacity to capacity-1
            heapq.heappush(self.pq, index)
            # take the top plate, pop it and return its value
            return self.stk[index].pop()
        # otherwise, return -1 because we can't pop any plate
        else:
            return -1


# 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)


class DinnerPlates:
    #Use heap to store index of available stack
    def __init__(self, capacity: int):
        self.cap = capacity
        self.stacks = []
        self.heap = []

    def push(self, val: int) -> None:
        #While exists heap and most left items in the stack that are full -> pop stack 
        while self.heap and self.heap[0] < len(self.stacks) and len(self.stacks[self.heap[0]]) == self.cap:
            heapq.heappop(self.heap)
        
        #If heap is empty -> need to insert in next index
        if not self.heap:
            heapq.heappush(self.heap, len(self.stacks))
        
        #If first item in heap has index == len(stacks) = last_index + 1, need to insert to next [array]
        if self.heap[0] == len(self.stacks):
            self.stacks.append([])
            
        self.stacks[self.heap[0]].append(val)
        
            
    def pop(self) -> int:
        while self.stacks and self.stacks[-1] == []:
            self.stacks.pop()
            
        return self.popAtStack(len(self.stacks)-1)

    def popAtStack(self, index: int) -> int:
        if 0<=index<len(self.stacks) and self.stacks[index] != []:
            heapq.heappush(self.heap, index)
            return self.stacks[index].pop()
        
        return -1
            

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.s = [[]]
        self.c= capacity
        self.head = 0 # leftmost unfilled array index
        self.tail = 0 # righmost non-empty array index

    def push(self, val: int) -> None:
        i=0
        self.s[self.head].append(val)
        self.tail = max(self.head, self.tail)
        
        while self.head<len(self.s) and len(self.s[self.head])==self.c:
            self.head +=1
        if self.head==len(self.s):
            self.s.append([])
        #self.tail = max(self.)
            
    def pop(self) -> int:
        if 0<=self.tail<len(self.s):
            res = self.s[self.tail].pop()
            while self.tail>=0 and len(self.s[self.tail])==0:
                self.tail -=1
            return res
        
        return -1
    

    def popAtStack(self, index: int) -> int:
        if index >= len(self.s):
            return -1
        if not self.s[index]:
            return -1
        res = self.s[index].pop()
        self.head = min(index, self.head)
        while self.tail>0 and len(self.s[self.tail])==0:
            self.tail -=1
        return res
        


# 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)


import heapq

class DinnerPlates:

    def __init__(self, capacity: int):
        self.C = capacity
        self.S = [[]]
        self.PQ = [0]
        self.M = 0

    def push(self, val: int) -> None:
        if not self.PQ:
            self.S.append([])
            heapq.heappush(self.PQ, len(self.S)-1)
            
        tmp = heapq.heappop(self.PQ)
        self.M = max(self.M, tmp)
        self.S[tmp].append(val)
        if len(self.S[tmp]) < self.C:
            heapq.heappush(self.PQ, tmp)
        

    def pop(self) -> int:
        tmp = self.M
        while tmp > 0 and not self.S[tmp]:
            tmp -= 1
        self.M = tmp
        if not self.S[tmp]:
            return -1
        if len(self.S[tmp]) == self.C:
            heapq.heappush(self.PQ, tmp)
        return self.S[tmp].pop()
        

    def popAtStack(self, index: int) -> int:
        if len(self.S) > index and self.S[index]:
            if len(self.S[index]) == self.C:
                heapq.heappush(self.PQ, index)
            return self.S[index].pop()
        else:
            return -1


# 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)


from collections import defaultdict
from heapq import heappush, heappop

class DinnerPlates:

    def __init__(self, capacity: int):
        self.size = capacity
        self.stacks = []
        self.left_available  = [] # min_heap
        
    def push(self, val: int) -> None:
        # clean up available stacks (which are actually unavailable)
        while self.left_available  and self.left_available [0] < len(self.stacks) and len(self.stacks[self.left_available [0]]) == self.size:
            heappop(self.left_available )
            
        # now we are at the leftmost available stack (if any)
        
        if not self.left_available :
            heappush(self.left_available , len(self.stacks))
            
        # check if the leftmost available stack exist before, or should we create it
        if self.left_available [0] == len(self.stacks):
            self.stacks.append([])
            
        self.stacks[self.left_available [0]].append(val)
        
            
    def pop(self) -> int:
        
        # clean up empty stacks
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        
        # now we are at the rightmost non-empty stack (if any)
        
        return self.popAtStack(len(self.stacks) - 1)

    
    def popAtStack(self, index: int) -> int:
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            
            # !! here we could add duplicate index, but it's ok, since we clean up in the push 
            heappush(self.left_available , index)
            return self.stacks[index].pop()
        
        return -1
            
        
        

# 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)


import heapq
class DinnerPlates:
    def __init__(self, capacity: int):
        # record values of all stack of plates, its last nonempty stack are the rightmost position
        self.stk = []
        self.c = capacity
        # record the available stack, will use heap to quickly find the smallest available stack
        self.pq = []

    def push(self, val: int) -> None:
        # Time: O(logN)
        # To push, we need to find the leftmost available position. first, let's remove any stacks on the left that are full
        while self.pq and self.pq[0] < len(self.stk) and len(self.stk[self.pq[0]]) == self.c:
            heapq.heappop(self.pq)
        
        # if the q is empty, meaning there are no more available stacks
        if len(self.pq) == 0:
            heapq.heappush(self.pq, len(self.stk))
        
        # for the newly added stack, add a new stack to self.stacks accordingly
        if self.pq[0] == len(self.stk):
            self.stk.append([])
        
        # append the value to the leftmost available stack
        self.stk[self.pq[0]].append(val)

    def pop(self) -> int:
        # Time: amortized O(1)
        # To pop, we need to find the rightmost nonempty stack
        # 1) stacks is not empty (self.stacks) and
        # 2) the last stack is empty
        while len(self.stk) > 0 and len(self.stk[-1]) == 0:
            self.stk.pop()
         
        return self.popAtStack(len(self.stk) - 1)

    def popAtStack(self, index: int) -> int:
        # Time: O(logN)
        # To pop from an stack of given index, we need to make sure that it is not empty
        # 1) the index for inserting is valid and，
        # 2) the stack of interest is not empty
        if 0 <= index < len(self.stk) and len(self.stk[index]):
            # we add the index into the available stack
            # heapq.heappush(self.pq, index)
            if len(self.stk[index]) == self.c:
                heapq.heappush(self.pq, index)
            # take the top plate, pop it and return its value
            return self.stk[index].pop()
        # otherwise, return -1 because we can't pop any plate
        else:
            return -1


# 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)


from collections import defaultdict
from heapq import heappush, heappop

class DinnerPlates:

    def __init__(self, capacity: int):
        self.size = capacity
        self.stacks = []
        self.leftmost_available = [] # min_heap
        
    def push(self, val: int) -> None:
        # clean up available stacks (which are actually unavailable)
        while self.leftmost_available and self.leftmost_available[0] < len(self.stacks) and len(self.stacks[self.leftmost_available[0]]) == self.size:
            heappop(self.leftmost_available)
            
        # now we are at the leftmost available stack (if any)
        
        if not self.leftmost_available:
            heappush(self.leftmost_available, len(self.stacks))
            
        # check if the leftmost available stack exist before, or should we create it
        if self.leftmost_available[0] == len(self.stacks):
            self.stacks.append([])
            
        self.stacks[self.leftmost_available[0]].append(val)
        
            
    def pop(self) -> int:
        
        # clean up empty stacks
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        
        # now we are at the rightmost non-empty stack (if any)
        
        return self.popAtStack(len(self.stacks) - 1)

    
    def popAtStack(self, index: int) -> int:
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            
            # !! here we could add duplicate index, but it's ok, since we clean up in the push 
            heappush(self.leftmost_available, index)
            return self.stacks[index].pop()
        
        return -1
            
        
        

# 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)


import heapq
class DinnerPlates:
    def __init__(self, capacity: int):
        # record values of all stack of plates, its last nonempty stack are the rightmost position
        self.stk = []
        self.c = capacity
        # record the available stack, will use heap to quickly find the smallest available stack
        self.pq = []

    def push(self, val: int) -> None:
        # Time: O(logN)
        # To push, we need to find the leftmost available position. first, let's remove any stacks on the left that are full
        while self.pq and self.pq[0] < len(self.stk) and len(self.stk[self.pq[0]]) == self.c:
            heapq.heappop(self.pq)
        
        # if the q is empty, meaning there are no more available stacks
        if len(self.pq) == 0:
            heapq.heappush(self.pq, len(self.stk))
        
        # for the newly added stack, add a new stack to self.stacks accordingly
        if self.pq[0] == len(self.stk):
            self.stk.append([])
        
        # append the value to the leftmost available stack
        self.stk[self.pq[0]].append(val)

    def pop(self) -> int:
        # Time: amortized O(1)
        # To pop, we need to find the rightmost nonempty stack
        # 1) stacks is not empty (self.stacks) and
        # 2) the last stack is empty
        while len(self.stk) > 0 and len(self.stk[-1]) == 0:
            self.stk.pop()
         
        return self.popAtStack(len(self.stk) - 1)

    def popAtStack(self, index: int) -> int:
        # Time: O(logN)
        # To pop from an stack of given index, we need to make sure that it is not empty
        # 1) the index for inserting is valid and，
        # 2) the stack of interest is not empty
        if 0 <= index < len(self.stk) and len(self.stk[index]):
            # we add the index into the available stack
            heapq.heappush(self.pq, index)
            # if len(self.stk[index]) == self.c:
            #     heapq.heappush(self.pq, index)
            # take the top plate, pop it and return its value
            return self.stk[index].pop()
        # otherwise, return -1 because we can't pop any plate
        else:
            return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.l, self.r, self.cnt = 0, 0, 0
        self.dic = {}
        self.dic[0] = []

    def push(self, val: int) -> None:
        while self.l in self.dic and len(self.dic[self.l]) == self.c:
            self.l += 1
        if self.l not in self.dic:
            self.dic[self.l] = []
        self.dic[self.l].append(val)
        self.cnt += 1
        self.r = max(self.l, self.r)
        
    def pop(self) -> int:
        if not self.cnt:
            return -1
        while self.r >= 0 and not self.dic[self.r]:
            self.r -= 1
        self.cnt -= 1
        self.l = min(self.l, self.r)
        return self.dic[self.r].pop()

    def popAtStack(self, index: int) -> int:
        if index not in self.dic or not self.dic[index]:
            return -1
        self.cnt -= 1
        self.l = min(self.l, index)
        return self.dic[index].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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.stacks = []
        self.idx = []

    def push(self, val: int) -> None:
        if self.idx and 0 <= self.idx[0] < len(self.stacks):
            i = self.idx[0]
            st = self.stacks[i]
            st.append(val)
            if len(st) == self.cap:
                heapq.heappop(self.idx)
        else:
            self.idx.clear()
            self.stacks.append([val])
            if self.cap > 1:
                self.idx.append(len(self.stacks) - 1)                        
        
    def pop(self) -> int:
        if not self.stacks:
            return -1
        st = self.stacks[-1]
        val = st.pop()
        if len(st) == self.cap - 1:
            heapq.heappush(self.idx, len(self.stacks) - 1)
        self._clean()
        return val

    def popAtStack(self, index: int) -> int:
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            st = self.stacks[index]
            val = st.pop()
            if len(st) == self.cap - 1:
                heapq.heappush(self.idx, index)
            self._clean()
            return val
        return -1
    
    def _clean(self):
        while self.stacks and not self.stacks[-1]:
            self.stacks.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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.stacks = []
        self.q = [] # heap of indices

    def push(self, val: int) -> None:
        # find leftmost location
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            heapq.heappop(self.q)
        
        if not self.q:
            heapq.heappush(self.q, len(self.stacks))
        if self.q[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.q[0]].append(val)
        

    def pop(self) -> int:
        # remove empty stacks from end
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        
        return self.popAtStack(len(self.stacks)-1)
        
    def popAtStack(self, index: int) -> int:
        if 0<=index<len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.q, index)
            return self.stacks[index].pop()
        return -1
            

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = [[]]
        self.capacity = capacity
        self.current = 0

    def push(self, val: int) -> None:
        if len(self.stacks) <= self.current:
            self.stacks.append([])
        self.stacks[self.current].append(val)
        i = self.current
        while len(self.stacks) > i and len(self.stacks[i]) == self.capacity:
            i += 1
        if len(self.stacks) == i:
            self.stacks.append([])
        self.current = i
        
        

    def pop(self) -> int:
        l = len(self.stacks) - 1
        while l >= 0 and not self.stacks[l]:
            self.stacks.pop()
            l -= 1
        if l == -1:
            self.current = 0
            self.stacks = [[]]
            return -1
        else:
            return self.stacks[l].pop()    
            

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks):
            return -1
        if not self.stacks[index]:
            return -1
        else:
            v = self.stacks[index].pop()
            if index < self.current:
                self.current = index
            return v
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stack_list = []
        self.available_stacks = []

    def push(self, val: int) -> None:
        if not self.available_stacks:
            self.stack_list.append([])
            self.available_stacks.append(len(self.stack_list) - 1)
        first_available_stack = self.available_stacks[0]
        self.stack_list[first_available_stack].append(val)
        if len(self.stack_list[first_available_stack]) == self.capacity:
            heapq.heappop(self.available_stacks)
        self.remove_empty_stacks_at_the_end()
    
    def remove_empty_stacks_at_the_end(self):
        while self.stack_list and not self.stack_list[-1]:
            self.stack_list.pop()
        while self.available_stacks and self.available_stacks[0] >= len(self.stack_list):
            heapq.heappop(self.available_stacks)
    
    def pop(self) -> int:
        return self.popAtStack(len(self.stack_list) - 1)     
        
    def popAtStack(self, index: int) -> int:
        if index < 0 or index >= len(self.stack_list) or not self.stack_list[index]:
            return -1
        if len(self.stack_list[index]) == self.capacity:
            heapq.heappush(self.available_stacks, index)
        result = self.stack_list[index].pop()
        self.remove_empty_stacks_at_the_end()
        return result


# 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)


class DinnerPlates:

    def __init__(self, capacity):
        self.c = capacity
        self.q = [] # record the available stack, will use heap to quickly find the smallest available stack
        # if you are Java or C++ users, tree map is another good option.
        self.stacks = [] # record values of all stack of plates, its last nonempty stack are the rightmost position

    def push(self, val):
        # To push, we need to find the leftmost available position
        # first, let's remove any stacks on the left that are full
        # 1) self.q: if there is still available stack to insert plate
        # 2) self.q[0] < len(self.stacks): the leftmost available index self.q[0] is smaller than the current size of the stacks
        # 3) len(self.stacks[self.q[0]]) == self.c: the stack has reached full capacity
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            # we remove the filled stack from the queue of available stacks
            heapq.heappop(self.q)

        # now we reach the leftmost available stack to insert

        # if the q is empty, meaning there are no more available stacks
        if not self.q:
            # open up a new stack to insert
            heapq.heappush(self.q, len(self.stacks))

        # for the newly added stack, add a new stack to self.stacks accordingly
        if self.q[0] == len(self.stacks):
            self.stacks.append([])

        # append the value to the leftmost available stack
        self.stacks[self.q[0]].append(val)

    def pop(self):
        # To pop, we need to find the rightmost nonempty stack
        # 1) stacks is not empty (self.stacks) and
        # 2) the last stack is empty
        while self.stacks and not self.stacks[-1]:
            # we throw away the last empty stack, because we can't pop from it
            self.stacks.pop()

        # now we reach the rightmost nonempty stack

        # we pop the plate from the last nonempty stack of self.stacks by using popAtStack function
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index):
        # To pop from an stack of given index, we need to make sure that it is not empty
        # 1) the index for inserting is valid and，
        # 2) the stack of interest is not empty
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            # we add the index into the available stack
            heapq.heappush(self.q, index)
            # take the top plate, pop it and return its value
            return self.stacks[index].pop()

        # otherwise, return -1 because we can't pop any plate
        return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.stack = []
        self.cap = capacity
        self.left = 0
        self.right = 0
        

    def push(self, val: int) -> None:
        if not self.stacks:
            self.stack.append(val)
            self.stacks.append(self.stack)
        else:
            while self.left < len(self.stacks) and len(self.stacks[self.left]) == self.cap:
                self.left += 1
            if self.left == len(self.stacks):
                self.stacks.append([])
                self.stacks[self.left].append(val)
                self.right = len(self.stacks) - 1
            else:
                self.stacks[self.left].append(val)
            
                

    def pop(self) -> int:
        if not self.stacks:
            return -1
        if not self.stacks[self.right]:
            while not self.stacks[self.right]:
                self.stacks.pop()
                self.right -= 1
        item = self.stacks[self.right].pop()
        
        if not self.stacks[self.right]:
            self.stacks.pop()
            self.right -= 1
        return item
                
        

    def popAtStack(self, index: int) -> int:
        if index > len(self.stacks) - 1:
            return -1
        if not self.stacks[index]:
            return -1
        if self.stacks[index]:
            if self.left > index:
                self.left = index
            item = self.stacks[index].pop()
            return item


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.stacks = []
        # Prio queue (heap)
        self.h = []

    def push(self, val: int) -> None:
        
        # As we can have multiple time same index in heap, we clean if stack have been fulled
        while self.h and self.h[0] < len(self.stacks) and len(self.stacks[self.h[0]]) == self.c:
            heapq.heappop(self.h)
        
        # Prio queue is empty, we declare a new list, store it's index
        if not self.h:
            heapq.heappush(self.h, len(self.stacks))
        
        #create or re-create new stack (heap can still ref a stack that have been deleted from stacks after multiple pop)
        if self.h[0] == len(self.stacks):
            self.stacks.append([])
        
        self.stacks[self.h[0]].append(val)

    def pop(self) -> int:
        
        # We clean emptied stacks
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        
        return self.popAtStack(len(self.stacks)-1)

    def popAtStack(self, index: int) -> int:
        
        # Can have multiple time same index in the heap (else we would need to check if elem in heap O(n))
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.h, index)
            
            return self.stacks[index].pop()
        return -1
    
    

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stack = [[[], capacity]]
        self.openSlot = [0]
        self.capacity = capacity
    
    def insertAt(self, x):
        l = 0
        r = len(self.openSlot) - 1
        if x < self.openSlot[l]:
            return 0
        if x > self.openSlot[r]:
            return l + 1
        while r > l:
            m = (r + l) // 2
            if self.openSlot[m] < x:
                l = m + 1
            else:
                r = m
        return l 
        
    def push(self, val: int) -> None:
        stackIndex = self.openSlot[0]
        self.stack[stackIndex][0].append(val)
        self.stack[stackIndex][1] -= 1
        if self.stack[stackIndex][1] == 0:
            self.openSlot.pop(0)
        if self.openSlot == []:
            self.stack.append([[], self.capacity])
            self.openSlot.append(len(self.stack)-1)
        
    def pop(self) -> int:
        while self.stack != [] and self.stack[-1][1] == self.capacity:
            self.stack.pop(-1)
            self.openSlot.pop(-1)
        if self.stack == []:
            self.stack.append([[], self.capacity])
            self.openSlot.append(len(self.stack)-1)
            return -1
        poppedVal = self.stack[-1][0].pop(-1)
        self.stack[-1][1] += 1
        if self.stack[-1][1] == 1:
            self.openSlot.insert(len(self.openSlot)-1, len(self.stack)-2)
        return poppedVal
        
    def popAtStack(self, index: int) -> int:
        if index >= len(self.stack) or self.stack[index][0] == []:
            return -1
        poppedVal = self.stack[index][0].pop(-1)
        self.stack[index][1] += 1
        if self.stack[index][1] == 1:
            self.openSlot.insert(self.insertAt(index), index)
        return poppedVal
# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks = []
        self.leftFreeIndex = 0
        self.rightOccupiedIndex = 0
    
    def seek_head(self):
        while self.leftFreeIndex < len(self.stacks) and len(self.stacks[self.leftFreeIndex]) == self.capacity:
            self.leftFreeIndex += 1
    
    def seek_tail(self):
        while self.rightOccupiedIndex > 0 and len(self.stacks[self.rightOccupiedIndex]) == 0:
            self.rightOccupiedIndex -= 1
        
    def push(self, val: int) -> None:
        if not self.stacks:
            self.stacks.append([])
            
        self.stacks[self.leftFreeIndex].append(val)
        self.rightOccupiedIndex = max(self.leftFreeIndex, self.rightOccupiedIndex)
        
        if len(self.stacks[self.leftFreeIndex]) == self.capacity:
            self.seek_head()
            if len(self.stacks) == self.leftFreeIndex:
                self.stacks.append([])
        
    def pop(self) -> int:
        #print('pop: ', self.stacks)
        if not self.stacks:
            #print('stacks is empty, no more stacks')
            return -1
        
        if self.stacks[self.rightOccupiedIndex]:
            val = self.stacks[self.rightOccupiedIndex].pop(-1)
            self.seek_tail()
            return val
        
        return -1

    def popAtStack(self, index: int) -> int:
        #print('popAtStack: ', index, ' with current stacks: ', self.stacks)
        if index > len(self.stacks)-1:
            #print('stack at index doesnt exists')
            return -1
        
        if index == self.rightOccupiedIndex and index < self.leftFreeIndex:
            val = self.stacks[index].pop(-1)
            self.leftFreeIndex = index
            self.seek_tail()
            return val
        
        if index < self.leftFreeIndex:
            val = self.stacks[index].pop(-1)
            self.leftFreeIndex = index
            return val
        
        if index == self.rightOccupiedIndex:
            val = self.stacks[index].pop(-1)
            self.seek_tail()
            return val
        
        if self.stacks[index]:
            return self.stacks[index].pop(-1)
        
        return -1
# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity #capacity
        self.stacks = [[]] #empty stack with the first stack
        self.stack_num = 1 #total of active (used) stack number
        self.stack_used = [] #order from left to right where there is an empty space
        self.stack_used.append(0) #the first stack is ready
        print(capacity)

    def cleanEmptyTail(self) -> None:
        i = self.stack_num - 1
        while i > 0 and len(self.stacks[i]) == 0 and len(self.stacks[i-1]) == 0:
            self.stacks.pop()
            self.stack_used.pop()
            self.stack_num -= 1
            i -= 1
        
    def push(self, val: int) -> None:
        # assert len(stack_used) > 0, a valid state
        i = self.stack_used[0] # return the left most stack number
        self.stacks[i].append(val)
        if len(self.stacks[i]) < self.capacity:
            # print('push', val)
            # print(self.stacks)
            # print(self.stack_used)
            return
        # now start to check this stack is full
        del self.stack_used[0] # this stack is not available
        if len(self.stack_used) == 0:
            # start to get the next one
            self.stacks.append([])
            self.stack_used.append(self.stack_num)
            self.stack_num += 1
        # print('push', val)
        # print(self.stacks)
        # print(self.stack_used)
        return

    def pop(self) -> int:
        # it's possible the rightmost stack is empty in the algorithm when it is just prepared.
        i = self.stack_num - 1
        if len(self.stacks[i]) == 0: #the algorithm should guarantee that there is not more than two empty
            # we have to remove this stack if it's not the leftmost one.
            if i == 0:
                return -1
            self.stacks.pop()
            self.stack_used.pop()
            self.stack_num -= 1
            i = self.stack_num -1
        # now remove this one from stack
        val = self.stacks[i].pop()
        if len(self.stack_used) == 0 or self.stack_used[-1] != i: 
            self.stack_used.append(i)
        # clean rightmost empty stacks
        self.cleanEmptyTail()
        # return value
        # print('p')
        # print(self.stacks)
        # print(self.stack_used)
        return val
    
    def insertUsed(self, index: int) -> None:
        head = 0
        end = len(self.stack_used) - 1
        while end - head > 1:
            i = (head + end) // 2
            mid_index = self.stack_used[i]
            if mid_index == index: 
                return # already there
            if mid_index > index:
                end = i
            else:
                head = i
        # 5 positions _ head _ end _
        if self.stack_used[head] > index:
            self.stack_used.insert(head, index)
            return
        if self.stack_used[head] == index or self.stack_used[end] == index:
            return
        if self.stack_used[end] > index:
            self.stack_used.insert(end, index)
            return
        self.stack_used.append(index)
        return

    def popAtStack(self, index: int) -> int:
        if index >= self.stack_num:
            return -1
        if len(self.stacks[index]) == 0:
            return -1
        val = self.stacks[index].pop()
        # insert into the stack_used list
        self.insertUsed(index)
        # clean
        self.cleanEmptyTail()
        # print('pAt', index)
        # print(self.stacks)
        # print(self.stack_used)
        return val

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stack_list = []
        self.available_stacks = []

    def push(self, val: int) -> None:
        self.remove_empty_stacks_at_the_end()
        if not self.available_stacks:
            self.stack_list.append([])
            self.available_stacks.append(len(self.stack_list) - 1)
        first_available_stack = self.available_stacks[0]
        self.stack_list[first_available_stack].append(val)
        if len(self.stack_list[first_available_stack]) == self.capacity:
            heapq.heappop(self.available_stacks)
    
    def remove_empty_stacks_at_the_end(self):
        while self.stack_list and not self.stack_list[-1]:
            self.stack_list.pop()
        while self.available_stacks and self.available_stacks[0] >= len(self.stack_list):
            heapq.heappop(self.available_stacks)
    
    def pop(self) -> int:
        self.remove_empty_stacks_at_the_end()
        return self.popAtStack(len(self.stack_list) - 1)     
        
    def popAtStack(self, index: int) -> int:
        if index < 0 or index >= len(self.stack_list) or not self.stack_list[index]:
            return -1
        if len(self.stack_list[index]) == self.capacity:
            heapq.heappush(self.available_stacks, index)
        result = self.stack_list[index].pop()
        self.remove_empty_stacks_at_the_end()
        return result


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.capacity = capacity
        self.pq = []

    def push(self, val: int) -> None:
        while self.pq and self.pq[0] < len(self.stacks) and len(self.stacks[self.pq[0]]) == self.capacity:
            heapq.heappop(self.pq)
        if not self.pq:
            heapq.heappush(self.pq, len(self.stacks))
        if self.pq[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.pq[0]].append(val)

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index: int) -> int:
        if 0 <= index <= len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.pq, index)
            return self.stacks[index].pop()
        return -1

class DinnerPlates:

    def __init__(self, capacity: int):
        self.stack = [[]]
        self.heap = [0]
        self.cap = capacity
        
    def push(self, val: int) -> None:
        while self.heap[0]<len(self.stack) and len(self.stack[self.heap[0]])==self.cap:
            heapq.heappop(self.heap)
        
        if self.heap[0]==len(self.stack):
            self.stack.append([])
        self.stack[self.heap[0]].append(val)
        if len(self.stack[self.heap[0]])==self.cap:
            heapq.heappush(self.heap, len(self.stack))
        
    def pop(self) -> int:
        while self.stack and not self.stack[-1]:
            self.stack.pop()
        
        if not self.stack:
            return -1

        heapq.heappush(self.heap, len(self.stack)-1)
        return self.stack[-1].pop()
    
    def popAtStack(self, index: int) -> int:
        if index>=len(self.stack) or not self.stack[index]:
            return -1
        
        heapq.heappush(self.heap, index)
        return self.stack[index].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)


import heapq

class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stks = []
        self.queue = []
        self.idx2cnt = [0 for _ in range(100000 + 5)]
        
    def _leftmost_idx(self):
        ret = len(self.stks)
        while len(self.queue) > 0:
            idx = self.queue[0]
            if self.idx2cnt[idx] < self.capacity:
                ret = idx
                break
            else:
                heapq.heappop(self.queue)
        return ret
    
    def _rightmost_idx(self):
        idx = len(self.stks) - 1
        while idx >= 0 and self.idx2cnt[idx] == 0:
            idx -= 1
        return idx
    
    def _pop(self, idx):
        if self.idx2cnt[idx] == 0:
            return -1
        ret = self.stks[idx].pop()
        if self.idx2cnt[idx] == self.capacity:
            heapq.heappush(self.queue, idx)
        self.idx2cnt[idx] -= 1
        while idx > 0 and self.idx2cnt[idx] == 0 and idx == len(self.stks) - 1:
            self.stks.pop()
            idx -= 1
        return ret

    def push(self, val: int) -> None:
        idx = self._leftmost_idx()
        if idx == len(self.stks):
            self.stks.append([])
            heapq.heappush(self.queue, idx)
        self.stks[idx].append(val)
        self.idx2cnt[idx] += 1

    def pop(self) -> int:
        idx = self._rightmost_idx()
        return self._pop(idx)

    def popAtStack(self, index: int) -> int:
        return self._pop(index)


# 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)


class DinnerPlates:
    
    def __init__(self, capacity):
        
        self.stacks = []
        self.stack = []
        self.capacity = capacity
        self.left = 0
        self.right = 0

    def push(self, val):
        #when stack is initially empty
        if not self.stacks:            
            self.stack.append(val)
            self.stacks.append(self.stack)
            self.left = 0   
        else:   
            #find the leftmost stack with capacity less than capacity to append item
            while self.left < len(self.stacks) and len(self.stacks[self.left]) == self.capacity:
                self.left += 1
            if self.left == len(self.stacks):
                self.stacks.append([])
                self.stacks[self.left].append(val)
            else:
                self.stacks[self.left].append(val)                
                        
            self.right = len(self.stacks) - 1

    def pop(self):
        if not self.stacks:
            return -1
        #find the rightmost non empty stack
        if not self.stacks[self.right]:
            while not self.stacks[self.right] and len(self.stacks) - 1 >= self.right:                
                self.stacks.pop(self.right)
                self.right -= 1
                
        item = self.stacks[self.right].pop() 
        
        #if stack gets empty after pop item, move the pointer for rightmost non empty stack
        if not self.stacks[self.right]:
            self.stacks.pop(self.right)
            self.right -= 1           
        
        return item                        
        
    def popAtStack(self, index):
        
        if len(self.stacks) - 1 < index:
            return -1
        if not self.stacks[index]:
            return -1
        
        #before popping item from stack at index, update the pointer for leftmost stack with capacity
        if self.stacks[index]:
            if self.left > index:
                self.left = index
        return self.stacks[index].pop()
    
    
    # self made, TLE
#     def __init__(self, capacity: int):
#         self.stacks = []
#         self.capacity = capacity

#     def push(self, val: int) -> None:
#         if not self.stacks:
#             self.stacks.append([])
#         for i in range(len(self.stacks)):
#             if len(self.stacks[i]) < self.capacity:
#                 self.stacks[i].append(val)
#                 break
#         else:
#             self.stacks.append([val])

#     def pop(self) -> int:    
#         if not self.stacks:
#             return -1
#         pop_val = None
#         for i in range(len(self.stacks) - 1, -1, -1):
#             if self.stacks[i]:
#                 pop_val = self.stacks[i].pop()
#                 if not self.stacks[i]:
#                     del self.stacks[i]
#                 break
#             else:
#                 self.stacks.pop()

#         return pop_val if pop_val else -1
        
#     def popAtStack(self, index: int) -> int:
#         if index >= len(self.stacks):
#             return -1
#         pop_val = None
#         if self.stacks[index]:
#             pop_val = self.stacks[index].pop()
#         return pop_val if pop_val else -1


# 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)


import heapq
class DinnerPlates:

    def __init__(self, capacity: int):
        self.stack = [] # just one array to simulate all the stacks
        self.cap = capacity 
        self.idx = [] # min-heap to track empty indicies

    def push(self, val: int) -> None:
        if len(self.idx) > 0:
            while len(self.idx) > 0:
                i = heappop(self.idx) 
                # Given that we just push index but don't validate the cache while
                # poping we need to check if this index is within current limits
                if i < len(self.stack):
                    self.stack[i] = val
                    return 
                
        # we didn't find empty spaces so we add to the end
        self.stack.append(val)

    def pop(self) -> int:
        n = len(self.stack) - 1
        if n < 0:
            return -1
        
        while n > -1:
            if self.stack[n] != -1:
                v = self.stack[n]
                self.stack[n] = -1
                # Add the empty index to the heap
                heappush(self.idx , n)
                return v
            else:
                # Because those appear at the end the list we free those memory spaces so
                # later pop operations are optimized
                del(self.stack[n])
            n -= 1
            
        # All stacks are empty
        return -1

    def popAtStack(self, index: int) -> int:
        # additional check that is [optional] just to skip any effort 
        # if index is already out of current limits
        count = len(self.stack) // self.cap
        if index > count:
            return -1
        
        # capture the boundaries of this stack
        leftptr = (index * self.cap) 
        rightptr = leftptr + self.cap - 1
        if rightptr > (len(self.stack) - 1): # edge case
            rightptr = (len(self.stack) - 1)
            
        # traverse within the stack at this index until we empty it or we find an occupied location    
        while self.stack[rightptr] == -1 and rightptr >= leftptr:
            rightptr -=1
            
        # if it isn't empty it means we found occupied position
        if rightptr >= leftptr:
            v = self.stack[rightptr]
            self.stack[rightptr] = -1
            # Add the empty index to the heap
            heappush(self.idx , rightptr)
            return v
        else:
            return -1


# 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)


import heapq

class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.capacity = capacity
        self.toPush = []

    def push(self, val: int) -> None:
        if not self.stacks:
            self.stacks.append([val])
        else:
            if self.toPush and self.toPush[0] < len(self.stacks):
                i = heapq.heappop(self.toPush)
                self.stacks[i].append(val)
            else:
                self.stacks[-1].append(val)
                
        if len(self.stacks[-1]) == self.capacity:
            self.stacks.append([])

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop() 
            # self.toPush = min(self.toPush, len(self.stacks)-1)
        
        if not self.stacks:
            return -1
        
        return self.stacks[-1].pop()

    def popAtStack(self, index: int) -> int:
        if index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.toPush, index)
            return self.stacks[index].pop()
        return -1

class DinnerPlates:

    def __init__(self, capacity: int):
        self.q = [] #avaliable index for stack
        self.stacks = [] #a list of stack
        self.c = capacity

    def push(self, val: int) -> None:
        #find left most empty stack
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            heapq.heappop(self.q) #remove index of full stack
            
        if not self.q:
            heapq.heappush(self.q, len(self.stacks))
        if self.q[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.q[0]].append(val)
            
    def pop(self) -> int:
        #find right most
        while self.stacks and not self.stacks[-1]:#remove empty stack
            self.stacks.pop()
        if self.stacks and self.stacks[-1]:
            return self.popAtStack(len(self.stacks) - 1)
        else:
            return -1

    def popAtStack(self, index: int) -> int:
        if index >= 0 and index < len(self.stacks) and self.stacks[index]:
            if len(self.stacks[index]) == self.c:
            #if True:
                heapq.heappush(self.q, index) #add avalible index
            #print(self.q)
            return self.stacks[index].pop()
        else:
            return -1
            
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.s = [[]]
        self.cl = 0
        self.cr = 0

    def push(self, val: int) -> None:
        # print(self.s)
        while self.cl < len(self.s) and len(self.s[self.cl]) == self.c:
            self.cl += 1
        # print(self.cl)
        # print(self.s)
        if self.cl == len(self.s):
            self.s.append([]) 
        self.s[self.cl].append(val)
            
        
        if self.cl > self.cr:
            self.cr = self.cl

    def pop(self) -> int:
        
        while self.cr > 0 and not len(self.s[self.cr]):
            self.s.pop()
            self.cr -= 1
        if self.cr < self.cl:
            self.cl = self.cr
        
        if len(self.s[self.cr]) > 0:
            return self.s[self.cr].pop()
        return -1

    def popAtStack(self, index: int) -> int:
        if index < len(self.s):
            if len(self.s[index]) > 0:
                t = self.s[index].pop()
                if index < self.cl:
                    self.cl = index
                return t
        return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.q = [] #avaliable index for stack
        self.stacks = [] #a list of stack
        self.c = capacity

    def push(self, val: int) -> None:
        #find left most empty stack
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            heapq.heappop(self.q) #remove index of full stack
            
        if not self.q:
            heapq.heappush(self.q, len(self.stacks))
        if self.q[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.q[0]].append(val)
            
    def pop(self) -> int:
        #find right most
        while self.stacks and not self.stacks[-1]:#remove empty stack
            self.stacks.pop()
        if self.stacks and self.stacks[-1]:
            return self.popAtStack(len(self.stacks) - 1)
        else:
            return -1

    def popAtStack(self, index: int) -> int:
        if index >= 0 and index < len(self.stacks) and self.stacks[index]:
            #if len(self.stacks[index]) == self.c:
            if True:
                heapq.heappush(self.q, index) #add avalible index
            #print(self.q)
            return self.stacks[index].pop()
        else:
            return -1
            
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.arr = [[]]
        self.indices = [0]
        self.cap = capacity

    def push(self, val: int) -> None:
        while len(self.arr[self.indices[0]])==self.cap:
            heapq.heappop(self.indices)
            
        self.arr[self.indices[0]].append(val)
        if len(self.arr[self.indices[0]])==self.cap and self.indices[0]==len(self.arr)-1:
            heapq.heappush(self.indices, len(self.arr))
            self.arr.append([])

    def pop(self) -> int:
        while self.arr and not self.arr[-1]:
            self.arr.pop()
        
        if self.arr:
            heapq.heappush(self.indices, len(self.arr)-1)
            return self.arr[-1].pop()
        else:
            return -1
        
    def popAtStack(self, index: int) -> int:
        if index>=len(self.arr) or not self.arr[index]: return -1
        # print(index, self.arr)
        heapq.heappush(self.indices, index)
        return self.arr[index].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)


class DinnerPlates:

    def __init__(self, capacity: int):
        # use a heap to store all the index whose corresponding list is not full
        self.h = []
        self.m = -1
        self.d = {}
        self.c = capacity
        
    def push(self, val: int) -> None:
        if len(self.d) == 0 or len(self.h) == 0:
            self.m += 1
            self.h = [self.m]
            self.d[self.m] = []
            
        key = self.h[0]
        if key > self.m:
            self.m += 1
            self.h = [self.m]
            self.d[self.m] = []            
        
        if key not in self.d:
            self.d[key] = []
        
        self.d[key].append(val)
        
        if len(self.d[key]) == self.c:
            heapq.heappop(self.h)
        
    def pop(self) -> int:

        return self.popAtStack(self.m)

    def popAtStack(self, index: int) -> int:
        if len(self.d)==0 or index not in self.d or len(self.d[index])==0:
            return -1
        
        res = self.d[index].pop()

        if len(self.d[index]) == self.c-1:
            heapq.heappush(self.h, index)
        
        while self.m not in self.d or len(self.d[self.m])==0:
            if self.m in self.d:
                self.d.pop(self.m)
            self.m -= 1
            
            if self.m == -1:
                break
        
        return res

# 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)


class DinnerPlates:
    def __init__(self, capacity):
        self.c = capacity
        self.q = []
        self.stacks = []

    def push(self, val):
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            heapq.heappop(self.q)

        if not self.q:
            heapq.heappush(self.q, len(self.stacks))

        if self.q[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.q[0]].append(val)

    def pop(self):
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index):
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.q, index)
            return self.stacks[index].pop()
        return -1
        

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks=[]
        self.stack=[]
        self.size=capacity
        self.left=0
        self.right=0

        

    def push(self, val: int) -> None:
         if not self.stacks:            
            self.stack.append(val)
            self.stacks.append(self.stack)
            self.left=0
                           
         else:   
            #find the leftmost stack with size less than capacity to append item
            while self.left<len(self.stacks) and len(self.stacks[self.left])==self.size:
                self.left+=1
            if self.left==len(self.stacks):
                self.stacks.append([])
                self.stacks[self.left].append(val)
            else:
                self.stacks[self.left].append(val)                
                        
            self.right=len(self.stacks)-1
        

    def pop(self) -> int:
        if not self.stacks:
            return -1
        
        #find the rightmost non empty stack
        if not self.stacks[self.right]:
            while not self.stacks[self.right]:                
                self.stacks.pop(self.right)
                self.right-=1
                
        item=self.stacks[self.right].pop() 
        
        #if stack gets empty after pop item, move the pointer for rightmost non empty stack
        if not self.stacks[self.right]:
            self.stacks.pop(self.right)
            self.right-=1           
         
        return item       
        

    def popAtStack(self, index: int) -> int:
        if len(self.stacks)-1<index:
            return -1
        if not self.stacks[index]:
            return -1
        
        #before popping item from stack at index, update the pointer for leftmost stack with capacity
        if self.stacks[index]:
            if self.left>index:
                self.left=index
        return self.stacks[index].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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.indicies = []
        self.stacks = []
        self.cap = capacity
    
    def clean_stack(self):
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
            
    def push(self, val: int) -> None:
        while self.indicies:
            index = heappop(self.indicies)
            
            if index < len(self.stacks) and len(self.stacks[index]) < self.cap:
                self.stacks[index].append(val)
                return
        
        if self.stacks and len(self.stacks[-1]) < self.cap:
            self.stacks[-1].append(val)
        else:
            self.stacks.append([val])
        
    def pop(self) -> int:
        if not self.stacks:
            return -1
        else:
            res = self.stacks[-1].pop()
        
        if not self.stacks[-1]:
            self.clean_stack()
        else:
            heappush(self.indicies, len(self.stacks) - 1)
        
        return res

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks) or not self.stacks[index]:
            return -1
        
        res = self.stacks[index].pop()
        
        if not self.stacks[-1]:
            self.clean_stack()
        else:
            heappush(self.indicies, index)
        
        return res


# 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)


from collections import deque
import heapq

class DinnerPlates:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacklist = []
        self.minh = []

    def push(self, val: int) -> None:
        while len(self.minh) > 0:
            lms = heapq.heappop(self.minh)
            if len(self.stacklist) - 1 >= lms:
                self.stacklist[lms].append(val)
                break
        else:
            if len(self.stacklist) == 0 or len(self.stacklist[-1]) >= self.capacity:
                self.stacklist.append(deque())
            self.stacklist[-1].append(val)

    def pop(self) -> int:
        if len(self.stacklist) == 0:
            return -1

        while len(self.stacklist[-1]) == 0:
            del self.stacklist[-1]

        if len(self.stacklist) > 0:
            res = self.stacklist[-1].pop()
        else:
            res = -1

        if len(self.stacklist[-1]) == 0:
            del self.stacklist[-1]

        return res

    def popAtStack(self, index: int) -> int:
        if len(self.stacklist) - 1 < index or len(self.stacklist[index]) == 0:
            return -1
        else:
            res = self.stacklist[index].pop()
            heapq.heappush(self.minh, index)
            return res

class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.stack = []
        self.cap = capacity
        self.left = 0
        self.right = 0
        

    def push(self, val: int) -> None:
        if not self.stacks:
            self.stack.append(val)
            self.stacks.append(self.stack)
        else:
            while self.left < len(self.stacks) and len(self.stacks[self.left]) == self.cap:
                self.left += 1
            if self.left == len(self.stacks):
                self.stacks.append([])
                self.stacks[self.left].append(val)
            else:
                self.stacks[self.left].append(val)
            self.right = len(self.stacks) - 1
                

    def pop(self) -> int:
        if not self.stacks:
            return -1
        if not self.stacks[self.right]:
            while not self.stacks[self.right]:
                self.stacks.pop()
                self.right -= 1
        item = self.stacks[self.right].pop()
        
        if not self.stacks[self.right]:
            self.stacks.pop()
            self.right -= 1
        return item
                
        

    def popAtStack(self, index: int) -> int:
        if index > len(self.stacks) - 1:
            return -1
        if not self.stacks[index]:
            return -1
        if self.stacks[index]:
            if self.left > index:
                self.left = index
            item = self.stacks[index].pop()
            return item


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stack = [[]]
        self.leftmost = 0
        self.rightmost = 0
        

    def push(self, val: int) -> None:
        try:
            self._find_leftmost()
        except IndexError:
            self.stack.append([])
\t\t\t# updates the rightmost index if needed
            if self.leftmost >= self.rightmost:
                self.rightmost = self.leftmost

        self.stack[self.leftmost].append(val)
        
    def pop(self) -> int:
        try:
            self._find_rightmost()
        except IndexError:
            self.rightmost = 0
            return -1

        return self.stack[self.rightmost].pop()

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stack) or not self.stack[index]:
            return -1

        value = self.stack[index].pop()
        if index < self.leftmost:
            self.leftmost = index
        return value

    def _find_leftmost(self):
        while len(self.stack[self.leftmost]) >= self.capacity:
            self.leftmost += 1

    def _find_rightmost(self):
        while not self.stack[self.rightmost]:
            self.rightmost -= 1


import heapq

class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.q = []
        self.stacks = []

    def push(self, val: int) -> None:
        # Find the leftmost available stack
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.capacity:
            heapq.heappop(self.q)
        
        # If q is empty
        if not self.q:
            heapq.heappush(self.q, len(self.stacks))
            
        if self.q[0] == len(self.stacks):
            self.stacks.append([])
        
        self.stacks[self.q[0]].append(val)

    def pop(self) -> int:
        # Pop empty stack
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        
        return self.popAtStack(len(self.stacks)-1)
        

    def popAtStack(self, index: int) -> int:
        if 0<=index<len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.q, index)
            return self.stacks[index].pop()
            
        return -1
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stack = [[]]
        self.leftmost = 0
        self.rightmost = 0
        

    def push(self, val: int) -> None:
        try:
            self._find_leftmost()
        except IndexError:
            self.stack.append([])
\t\t\t# updates the rightmost index if needed
            if self.leftmost >= self.rightmost:
                self.rightmost = self.leftmost

        self.stack[self.leftmost].append(val)
        
    def pop(self) -> int:
        try:
            self._find_rightmost()
        except IndexError:
            self.rightmost = 0
            return -1

        return self.stack[self.rightmost].pop()

    def popAtStack(self, index: int) -> int:

        if index >= len(self.stack) or not self.stack[index]:
            return -1

        value = self.stack[index].pop()
        if index < self.leftmost:
            self.leftmost = index
        return value

    def _find_leftmost(self):
        while len(self.stack[self.leftmost]) >= self.capacity:
            self.leftmost += 1

    def _find_rightmost(self):
        while not self.stack[self.rightmost]:
            self.rightmost -= 1

class DinnerPlates:
    def __init__(self, capacity):
        self.c = capacity
        self.q = [] # record the available stack, will use heap to quickly find the smallest available stack
        # if you are Java or C++ users, tree map is another good option.
        self.stacks = [] # record values of all stack of plates, its last nonempty stack are the rightmost position

    def push(self, val):
        # To push, we need to find the leftmost available position
        # first, let's remove any stacks on the left that are full
        # 1) self.q: if there is still available stack to insert plate
        # 2) self.q[0] < len(self.stacks): the leftmost available index self.q[0] is smaller than the current size of the stacks
        # 3) len(self.stacks[self.q[0]]) == self.c: the stack has reached full capacity
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            # we remove the filled stack from the queue of available stacks
            heapq.heappop(self.q)

        # now we reach the leftmost available stack to insert

        # if the q is empty, meaning there are no more available stacks
        if not self.q:
            # open up a new stack to insert
            heapq.heappush(self.q, len(self.stacks))

        # for the newly added stack, add a new stack to self.stacks accordingly
        if self.q[0] == len(self.stacks):
            self.stacks.append([])

        # append the value to the leftmost available stack
        self.stacks[self.q[0]].append(val)

    def pop(self):
        # To pop, we need to find the rightmost nonempty stack
        # 1) stacks is not empty (self.stacks) and
        # 2) the last stack is empty
        while self.stacks and not self.stacks[-1]:
            # we throw away the last empty stack, because we can't pop from it
            self.stacks.pop()

        # now we reach the rightmost nonempty stack

        # we pop the plate from the last nonempty stack of self.stacks by using popAtStack function
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index):
        # To pop from an stack of given index, we need to make sure that it is not empty
        # 1) the index for inserting is valid and，
        # 2) the stack of interest is not empty
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            # we add the index into the available stack
            heapq.heappush(self.q, index)
            # take the top plate, pop it and return its value
            return self.stacks[index].pop()

        # otherwise, return -1 because we can't pop any plate
        return -1


class DinnerPlates:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.stacks = []
        self.heap = []
    def push(self, val: int) -> None:
        if self.heap and self.heap[0]>=len(self.stacks):
            self.heap = []
        if self.heap:
            if len(self.stacks[self.heap[0]]) < self.cap:
                self.stacks[self.heap[0]].append(val)
                if len(self.stacks[self.heap[0]]) == self.cap:
                    heapq.heappop(self.heap)
        else:
            self.stacks.append([val])
            if self.cap != 1:
                heapq.heappush(self.heap, len(self.stacks)-1)

    def pop(self) -> int:
        if not self.stacks:
            return -1
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        if self.stacks and len(self.stacks[-1]) == self.cap:
            heapq.heappush(self.heap, len(self.stacks)-1)
        return self.stacks[-1].pop() if self.stacks else -1

    def popAtStack(self, index: int) -> int:
        if len(self.stacks) <= index or not self.stacks[index]:
            return -1
        if len(self.stacks[index]) == self.cap:
            heapq.heappush(self.heap, index)
        return self.stacks[index].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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stack = []
        self.available_to_push = []   # min heap to store the idx of available-to-push stack

    def push(self, val: int) -> None:
        # step 1: pop out all the left stacks that are not avaliable to push, 
        # so that after the while loop, we will know the leftmost stack that is available to push
        while len(self.available_to_push) > 0 and self.available_to_push[0] < len(self.stack) and len(self.stack[self.available_to_push[0]]) == self.capacity:
            heappop(self.available_to_push)
            
        # if the q is empty, meaning there are no more available stacks
        if len(self.available_to_push) == 0:        
            heappush(self.available_to_push, len(self.stack))
        if self.available_to_push[0] == len(self.stack):
            self.stack.append([])
            
        # finally, we can push our val into the leftmost available stack
        self.stack[self.available_to_push[0]].append(val)

    def pop(self) -> int:
        # step 1: pop out all the empty stacks on the right, cuz they are not available to pop
        while len(self.stack) > 0 and len(self.stack[-1]) == 0:
            self.stack.pop()
            
        return self.popAtStack(len(self.stack) - 1)

    def popAtStack(self, index: int) -> int:
        # check if it is available to pop
        if 0 <= index < len(self.stack) and len(self.stack[index]) > 0:
            heappush(self.available_to_push, index)     # add this index to the available-to-push heap
            return self.stack[index].pop()
        return -1
        


# 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)


class DinnerPlates:
    def __init__(self, capacity):
        self.capacity = capacity
        self.heap = []
        self.stacks = []
    
    def push(self, val):
        while self.heap and self.heap[0] < len(self.stacks) and len(self.stacks[self.heap[0]]) == self.capacity:
            heapq.heappop(self.heap)
        
        if not self.heap:
            heapq.heappush(self.heap, len(self.stacks))
        if self.heap[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.heap[0]].append(val)
        
    def pop(self):
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        return self.popAtStack(len(self.stacks) - 1)
    
    def popAtStack(self, index):
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.heap, index)
            return self.stacks[index].pop()
        return -1
    
# 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)


from heapq import heappop, heappush
class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stack = []
        self.pop_q = []
        self.push_q = []
        

    def push(self, val: int) -> None:
        if self.pop_q:
            i = heappop(self.pop_q)
            self.stack[i] = val
        else:
            i = len(self.stack)
            self.stack.append(val)
        heappush(self.push_q, -i)
        

    def pop(self) -> int:
        if self.push_q:
            i = - heappop(self.push_q)
            while self.stack[i] == -1 and self.push_q:
                i = - heappop(self.push_q)
            if self.stack[i] != -1:
                heappush(self.pop_q, i)
                val = self.stack[i]
                self.stack[i] = -1
                return val
        return -1
        

    def popAtStack(self, index: int) -> int:
        start = index * self.capacity
        end = min(start + self.capacity - 1, len(self.stack) - 1)
        for i in range(end, start-1, -1):
            if self.stack[i] != -1:
                heappush(self.pop_q, i)
                val = self.stack[i]
                self.stack[i] = -1
                return val
        return -1
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):

        
        self.c = capacity
        # heap queue to find the leftmost available stack.
        self.q = []
        # a list stacks to save all stacks.
        self.stacks = [] 
        

    def push(self, val: int) -> None:
        # the leftmost available index self.q[0] is smaller than the current size of the stacks
        # the stack has reached full capacity
        while self.q and self.q[0] < len(self.stacks) and len(self.stacks[self.q[0]]) == self.c:
            # we remove the filled stack from the queue of available stacks
            heapq.heappop(self.q)

        # now we reach the leftmost available stack to insert

        # if the q is empty, no more available stacks
        if not self.q:
            # open up a new stack to insert
            heapq.heappush(self.q, len(self.stacks))

        # for the newly added stack, add a new stack to self.stacks accordingly
        if self.q[0] == len(self.stacks):
            self.stacks.append([])

        # append the value to the leftmost available stack
        self.stacks[self.q[0]].append(val)

    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            # we throw away the last empty stack, because we can't pop from it
            self.stacks.pop()

        # now we reach the rightmost nonempty stack

        # we pop the plate from the last nonempty stack of self.stacks by using popAtStack function
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index: int) -> int:
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            # we add the index into the available stack
            heapq.heappush(self.q, index)
            # take the top plate, pop it and return its value
            return self.stacks[index].pop()

        # otherwise, return -1 because we can't pop any plate
        return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.max = capacity
        self.top = 0
        self.stack = collections.defaultdict(list)
        self.stack[self.top] = [0, []]
        self.h = []; 
        heapq.heappush(self.h, 0)
        
    def push(self, val: int) -> None:
        
        ptr = heapq.heappop(self.h)
        self.stack[ptr][1].append(val)
        self.stack[ptr][0] += 1
        if self.stack[ptr][0]<self.max: heapq.heappush(self.h, ptr)
        elif ptr==self.top: 
            self.top += 1
            self.stack[self.top] = [0, []]
            heapq.heappush(self.h, self.top)

        
    def popAtStack(self, index: int) -> int:

        if not index in self.stack or not self.stack[index][0]: return -1
        if self.stack[index][0]==self.max:
            heapq.heappush(self.h, index)
        self.stack[index][0] -= 1
        return self.stack[index][1].pop() 
        
    def pop(self) -> int:
        while self.top  and not self.stack[self.top][0]:
            self.top -= 1
        return self.popAtStack(self.top)

        
        


# 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)


import heapq


class DinnerPlates:

    def __init__(self, capacity: int):
        self._stacks = []
        self._capacity = capacity
        self._start = 0

    def push(self, val: int) -> None:
        stack_idx = self._start
        while stack_idx < len(self._stacks):
            if len(self._stacks[stack_idx]) < self._capacity:
                break
            stack_idx += 1
        self._start = stack_idx
        if stack_idx == len(self._stacks):
            self._stacks.append([])        
        self._stacks[stack_idx].append(val)

    def pop(self) -> int:
        while self._stacks and not self._stacks[-1]:
            self._stacks.pop()
        if self._stacks:
            self._start = min(self._start, len(self._stacks[-1]) - 1)
            return self._stacks[-1].pop()
        else:
            return -1

    def popAtStack(self, index: int) -> int:
        if index < len(self._stacks) and self._stacks[index]:
            self._start = min(self._start, index)
            return self._stacks[index].pop()
        else:
            return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = [[]]
        self.capacity = capacity
        self.left = 0
        self.right = -1
        

    def push(self, val: int) -> None:
        self.stacks[self.left].append(val)
        if self.left > self.right:
            self.right = self.left
        if len(self.stacks[self.left]) == self.capacity:
            self.left = self.left + 1
            while True:
                if self.left <= len(self.stacks) - 1:
                    if len(self.stacks[self.left]) < self.capacity:
                        return None
                    else:
                        self.left = self.left + 1
                else:
                    self.stacks.append([])
                    return None

    def pop(self) -> int:
        if self.right == -1:
            return -1
        else:
            toreturn = self.stacks[self.right].pop()
            if self.stacks[self.right]:
                if self.left > self.right:
                    self.left = self.right
                return toreturn
            else:
                self.right = self.right - 1
                while True:
                    if self.right > -1:
                        if self.stacks[self.right]:
                            return toreturn
                        else:
                            self.right = self.right - 1
                    
                    return toreturn
                        

    def popAtStack(self, index: int) -> int:
        if index < len(self.stacks):
            if self.stacks[index]:
                if index < self.left:
                    self.left = index
                toreturn = self.stacks[index].pop()
                if not self.stacks[index] and index == self.right:
                                    self.right = self.right - 1
                while True:
                    if self.right > -1:
                        if self.stacks[self.right]:
                            return toreturn
                        else:
                            self.right = self.right - 1
                    
                    return toreturn
        return -1
            
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.stacks = []
        self.stack = []
        self.cap = capacity
        self.left = 0
        self.right = 0
        

    def push(self, val: int) -> None:
        if not self.stacks:
            self.stack.append(val)
            self.stacks.append(self.stack)
            self.left = 0
        else:
            while self.left < len(self.stacks) and len(self.stacks[self.left]) == self.cap:
                self.left += 1
            if self.left == len(self.stacks):
                self.stacks.append([])
                self.stacks[self.left].append(val)
            else:
                self.stacks[self.left].append(val)
            self.right = len(self.stacks) - 1
                

    def pop(self) -> int:
        if not self.stacks:
            return -1
        if not self.stacks[self.right]:
            while not self.stacks[self.right]:
                self.stacks.pop()
                self.right -= 1
        item = self.stacks[self.right].pop()
        
        if not self.stacks[self.right]:
            self.stacks.pop()
            self.right -= 1
        return item
                
        

    def popAtStack(self, index: int) -> int:
        if index > len(self.stacks) - 1:
            return -1
        if not self.stacks[index]:
            return -1
        if self.stacks[index]:
            if self.left > index:
                self.left = index
            item = self.stacks[index].pop()
            return item


# 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)


from queue import PriorityQueue
class DinnerPlates:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.stacks =[]
        self.q = PriorityQueue()

         

    def push(self, val: int) -> None:
        while self.stacks and not self.q.empty():
            idx = self.q.get()
            if idx > len(self.stacks) - 1:
                self.stacks.append([])
            # if len(self.stacks[idx]) == self.cap:
            #     continue
            # else:
            self.stacks[idx].append(val)
            if len(self.stacks[idx]) < self.cap:
                self.q.put(idx)
            return
        
        if not self.stacks:
            self.stacks = [[val]]
            if len(self.stacks[-1]) < self.cap:
                self.q.put(0)
        elif self.q.empty():
            self.stacks.append([val])
            if len(self.stacks[-1]) < self.cap:
                self.q.put(len(self.stacks) - 1)
        

    def pop(self) -> int:
        while self.stacks:
            if not self.stacks[-1]:
                del self.stacks[-1]
            else:
                v = self.stacks[-1][-1]
                del self.stacks[-1][-1]
                if len(self.stacks[-1]) == self.cap -1:
                    self.q.put(len(self.stacks) - 1)
                return v
        return -1
        

    def popAtStack(self, index: int) -> int:
        if index < len(self.stacks):
            l = self.stacks[index]
            if l:
                if len(l) == self.cap:
                    self.q.put(index)
                v = l.pop()
                return v
            else:
                return -1
        else:
            return -1
                
        
        


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.s = []
        self.h = []

    def push(self, val: int) -> None:
        # print(self.s)
        while self.h and self.h[0] < len(self.s) and len(self.s[self.h[0]]) == self.c:
            heapq.heappop(self.h)
        
        if not self.h:
            heapq.heappush(self.h, len(self.s))
            
        if self.h[0] == len(self.s):
            self.s.append([]) 
        self.s[self.h[0]].append(val)
            

    def pop(self) -> int:
        
        while  self.s and not self.s[-1]:
            self.s.pop()
            
        return self.popAtStack(len(self.s)-1)

    def popAtStack(self, index: int) -> int:
        # print(self.s)
        # print(self.h)
        if 0 <= index < len(self.s) and self.s[index]:
            heapq.heappush(self.h, index)
            return self.s[index].pop()
        return -1


# 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)


class DinnerPlates:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = []
        self.stacks = []

    def push(self, val):
        while self.queue and self.queue[0] < len(self.stacks) and len(self.stacks[self.queue[0]]) == self.capacity:
            heapq.heappop(self.queue)

        if not self.queue:
            heapq.heappush(self.queue, len(self.stacks))

        if self.queue[0] == len(self.stacks):
            self.stacks.append([])
        self.stacks[self.queue[0]].append(val)

    def pop(self):
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index):
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.queue, index)
            return self.stacks[index].pop()
        return -1
        

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.minHeap = []
        self.stacksTotal = []
        

    def push(self, val: int) -> None:
        while self.minHeap and self.minHeap[0] < len(self.stacksTotal) and len(self.stacksTotal[self.minHeap[0]]) == self.capacity:
            heapq.heappop(self.minHeap)
            
        
        if not self.minHeap:
            heapq.heappush(self.minHeap, len(self.stacksTotal))
        
        if self.minHeap[0] == len(self.stacksTotal):
            self.stacksTotal.append([])
        
        self.stacksTotal[self.minHeap[0]].append(val)
        
        
        
    def pop(self) -> int:
        while self.stacksTotal and not self.stacksTotal[-1]:
            self.stacksTotal.pop()
        
        return self.popAtStack(len(self.stacksTotal) - 1)
        
        
        

    def popAtStack(self, index: int) -> int:
        if 0<= index < len(self.stacksTotal) and self.stacksTotal[index]:
            heapq.heappush(self.minHeap, index)
            return self.stacksTotal[index].pop()
        
        return -1
        



import heapq
class DinnerPlates:

    def __init__(self, capacity: int):
        
        self.q = []
        self.c = capacity
        self.h = []

    def push(self, val: int) -> None:
        #print(\"Before Push: q:{}, h:{}\".format(self.q, self.h))
        if self.h:
            index = heapq.heappop(self.h)
            if index > len(self.q) - 1:
                self.h = []
                if self.q and self.q[-1] and len(self.q[-1]) < self.c:
                    self.q[-1] += [val]
                else:
                    self.q.append([val])
            else:
                if self.q[index]:
                    self.q[index] += [val]
                else:
                    self.q[index] = [val]
        else:
            if self.q and self.q[-1] and len(self.q[-1]) < self.c:
                self.q[-1] += [val]
            else:
                self.q.append([val])
        #print(\"after Push: q:{}, h:{}\".format(self.q, self.h))
                
    def pop(self) -> int:
        #print(\"POP q:{}\".format(self.q))
        while self.q:
            if self.q[-1]:
                item = self.q[-1].pop()
                if not self.q:
                    self.q.pop()
                #print(\"POP return q:{}, item:{}\".format(self.q, item))
                return item
            else:
                self.q.pop()
        return -1

    def popAtStack(self, index: int) -> int:
        
        #print(\"Index POP: index:{}, q:{}\".format(index, self.q))
        if index > len(self.q) - 1:
            return -1
        
        if self.q[index]:
            item = self.q[index].pop()
            heapq.heappush(self.h, index)
            return item
        else:
            return -1

# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.c = capacity
        self.s = []
        self.q = []

    def push(self, val: int) -> None:
        while self.q and (self.q[0] >= len(self.s) or len(self.s[self.q[0]]) == self.c):
            heapq.heappop(self.q)
        
        # print(self.q, self.s)
        if self.q:
            idx = self.q[0]
            self.s[idx].append(val)
            if len(self.s[idx]) == self.c:
                heapq.heappop(self.q)
        else:
            idx = len(self.s)-1
            if not self.s or len(self.s[-1]) == self.c:
                idx += 1
                self.s.append([])
            self.s[idx].append(val)

    def pop(self) -> int:
        while self.s and not self.s[-1]:
            self.s.pop()
        return self.popAtStack(len(self.s) - 1)

    def popAtStack(self, index: int) -> int:
        # print(self.s)
        if 0 <= index < len(self.s) and self.s[index]:
            heapq.heappush(self.q, index)
            return self.s[index].pop()
        return -1


# 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)


class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks = []
        self.tofill = []

    def push(self, val: int) -> None:
        while self.tofill and self.tofill[0] < len(self.stacks) and len(self.stacks[self.tofill[0]]) == self.capacity:
            heapq.heappop(self.tofill)
        
        if not self.tofill:
            heapq.heappush(self.tofill, len(self.stacks))
        
        if self.tofill[0] == len(self.stacks):
            self.stacks.append([])
        
        self.stacks[self.tofill[0]].append(val)
            
    def pop(self) -> int:
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
            
        return self.popAtStack(len(self.stacks) - 1)

    def popAtStack(self, index: int) -> int:
        if 0 <= index < len(self.stacks) and self.stacks[index]:
            heapq.heappush(self.tofill, index)
            return self.stacks[index].pop()
        return -1


# 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)