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 capacity.
	void push(int val) Pushes the given integer val into the leftmost stack with a 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 the stacks are empty.
	int popAtStack(int index) Returns the value at the top of the stack with the given index index and removes it from that stack or returns -1 if the stack with that given index is empty.


&nbsp;
Example 1:

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.


&nbsp;
Constraints:


	1 &lt;= capacity &lt;= 2 * 104
	1 &lt;= val &lt;= 2 * 104
	0 &lt;= index &lt;= 105
	At most 2 * 105 calls will be made to push, pop, and popAtStack.


class DinnerPlates:

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

    def push(self, val: int) -> None:
        if self.heap:
            index = heapq.heappop(self.heap)
            if index < len(self.stacks):
                self.stacks[index].append(val)
            else:
                self.push(val)
        elif self.stacks:
            lastStack = self.stacks[-1]
            if len(lastStack) != self.capacity:
                lastStack.append(val)
            else:
                stack = deque()
                stack.append(val)
                self.stacks.append(stack)
        else:
            stack = deque()
            stack.append(val)
            self.stacks.append(stack)
            
    def pop(self) -> int:
        while self.stacks:
            lastStack = self.stacks[-1]
            if lastStack:
                val = lastStack.pop()
                if not lastStack:
                    self.stacks.pop()
                return val
            else:
                self.stacks.pop()
        return -1

    def popAtStack(self, index: int) -> int:
        if index == len(self.stacks) - 1:
            return self.pop()
        if index < len(self.stacks):
            stack = self.stacks[index]
            if stack:
                val = stack.pop()
                heapq.heappush(self.heap, index)
                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 {
    
    List<Stack<Integer>> stack;
    PriorityQueue<Integer> leftEmpty;
    PriorityQueue<Integer> rightNonEmpty;
    int cap;
    public DinnerPlates(int capacity) {
        this.cap = capacity;
        this.stack = new ArrayList<>();
        this.leftEmpty = new PriorityQueue<>();
        this.rightNonEmpty = new PriorityQueue<>(Collections.reverseOrder());
        stack.add(new Stack<>());
        leftEmpty.offer(0);
    }
    
    public void push(int val) {
        while(!leftEmpty.isEmpty() && stack.get(leftEmpty.peek()).size() == cap) leftEmpty.poll();
        if(leftEmpty.isEmpty()) {
            stack.add(new Stack<>());
            leftEmpty.offer(stack.size() - 1);
        }
        Stack<Integer> s = stack.get(leftEmpty.peek());
        if(s.isEmpty()) rightNonEmpty.offer(leftEmpty.peek());
        s.push(val);
    }
    
    public int pop() {
        while(!rightNonEmpty.isEmpty() && stack.get(rightNonEmpty.peek()).isEmpty()) rightNonEmpty.poll();
        if(rightNonEmpty.isEmpty()) {
            return -1;
        }        
        Stack<Integer> s = stack.get(rightNonEmpty.peek());
        if(s.size() == cap) leftEmpty.offer(rightNonEmpty.peek());
        return s.pop();
    }
    
    public int popAtStack(int index) {
        if(index >= stack.size()) return -1;
        Stack<Integer> s = stack.get(index);
        if(s.isEmpty()) return -1;
        if(s.size() == cap) leftEmpty.offer(index);
        return s.pop();
    }
}

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates obj = new DinnerPlates(capacity);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAtStack(index);
 */
class DinnerPlates {
public:
    map<int,stack<int>>mp;
    set<int>empty;
    int cap;
    DinnerPlates(int capacity) 
    {
        this->cap=capacity;
    }
    
    void push(int val) 
    {
        if(empty.size()==0)
        {
            empty.insert(mp.size());
        }
        mp[*empty.begin()].push(val);
        if(mp[*empty.begin()].size()==cap)
        {
            empty.erase(empty.begin());
        }
    }
    int pop() 
    {
        if(mp.size()==0)
        {
            return -1;
        }
        int index=mp.rbegin()->first;
        int val=mp[index].top();
        mp[index].pop();
        empty.insert(index);
        if(mp[index].size()==0)
        {
            mp.erase(index);
        }
        return val;
    }
    
    int popAtStack(int index) 
    {
        if(mp.size()==0||mp.find(index)==mp.end())
        {
            return -1;
        }
        int val=mp[index].top();
        mp[index].pop();
        empty.insert(index);
        if(mp[index].size()==0)
        {
            mp.erase(index);
        }
        return val;
    }
};
/**
 * @param {number} capacity
 */
var DinnerPlates = function(capacity) {
    this.capacity = capacity;
    this.stacks = [];
};

/** 
 * @param {number} val
 * @return {void}
 */
DinnerPlates.prototype.push = function(val) {
    var needNewStack = true
    for (var i = 0; i < this.stacks.length; i++) {
        if (this.stacks[i].length < this.capacity) {
            this.stacks[i].push(val);
            needNewStack = false;
            break;
        }
    }
    
    if (needNewStack) {
        this.stacks.push([val]);
    }
    
};

/**
 * @return {number}
 */
DinnerPlates.prototype.pop = function() {
    var val = -1;
    for (var i = this.stacks.length - 1; i >= 0; i--) {
        if (this.stacks[i].length > 0) {
            val = this.stacks[i].pop();
            break;
        }
    }
    return val;
};

/** 
 * @param {number} index
 * @return {number}
 */
DinnerPlates.prototype.popAtStack = function(index) {
    // console.log(index, this.stacks, ...this.stacks[index])
    var val = -1;
    if (this.stacks[index] && this.stacks[index].length > 0) {
        val = this.stacks[index].pop()
    }
    return val;
};

/** 
 * Your DinnerPlates object will be instantiated and called as such:
 * var obj = new DinnerPlates(capacity)
 * obj.push(val)
 * var param_2 = obj.pop()
 * var param_3 = obj.popAtStack(index)
 */
Dinner Plate Stacks