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: MEDIUM
Tags: Data structures
Skill types: Data structures

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:

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

	def push(self, val: int) -> None:
		if len(self.idx) > 0:
			while len(self.idx) > 0:
				i = heappop(self.idx)
				if i < len(self.stack):
					self.stack[i] = val
					return
		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
				heappush(self.idx, n)
				return v
			else:
				del self.stack[n]
			n -= 1
		return -1

	def popAtStack(self, index: int) -> int:
		count = len(self.stack) // self.cap
		if index > count:
			return -1
		leftptr = index * self.cap
		rightptr = leftptr + self.cap - 1
		if rightptr > len(self.stack) - 1:
			rightptr = len(self.stack) - 1
		while self.stack[rightptr] == -1 and rightptr >= leftptr:
			rightptr -= 1
		if rightptr >= leftptr:
			v = self.stack[rightptr]
			self.stack[rightptr] = -1
			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


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


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.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


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:
		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:
		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

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


class DinnerPlates:

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

	def push(self, val: int) -> None:
		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


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

	def pop(self) -> int:
		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)
		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)
		return val


class DinnerPlates:

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

	def push(self, val: int) -> None:
		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 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([])
		self.stack[self.available_to_push[0]].append(val)

	def pop(self) -> int:
		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:
		if 0 <= index < len(self.stack) and len(self.stack[index]) > 0:
			heappush(self.available_to_push, index)
			return self.stack[index].pop()
		return -1


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])
		elif 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()
		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.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


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


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


class DinnerPlates:

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

	def push(self, val):
		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.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
		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 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
		if self.stacks[index]:
			if self.left > index:
				self.left = index
		return self.stacks[index].pop()


class DinnerPlates:

	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


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


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:
		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:
		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:
		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)
				elif 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


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


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


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]) == 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


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


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


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 = []

	def push(self, val):
		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:
					heappop(self.nonfull)
				return
			else:
				heappop(self.nonfull)
		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


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()
		elif 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.capacity and curlen == self.capacity and (index != len(self.stacks) - 1):
			heappush(self.heapnonfull, index)
		return self.stacks[index].pop()


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


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


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


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


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


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


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


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


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


import heapq

class DinnerPlates:

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

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

	def pop(self) -> int:
		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:
		if 0 <= index < len(self.stk) and len(self.stk[index]):
			heapq.heappush(self.pq, index)
			return self.stk[index].pop()
		else:
			return -1


class DinnerPlates:

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

	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([])

	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


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


from collections import defaultdict
from heapq import heappush, heappop

class DinnerPlates:

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

	def push(self, val: int) -> None:
		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)
		if not self.left_available:
			heappush(self.left_available, len(self.stacks))
		if self.left_available[0] == len(self.stacks):
			self.stacks.append([])
		self.stacks[self.left_available[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]:
			heappush(self.left_available, index)
			return self.stacks[index].pop()
		return -1


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


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


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


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:
		if not self.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:
		if index > len(self.stacks) - 1:
			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


class DinnerPlates:

	def __init__(self, capacity: int):
		self.capacity = capacity
		self.stacks = [[]]
		self.stack_num = 1
		self.stack_used = []
		self.stack_used.append(0)
		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:
		i = self.stack_used[0]
		self.stacks[i].append(val)
		if len(self.stacks[i]) < self.capacity:
			return
		del self.stack_used[0]
		if len(self.stack_used) == 0:
			self.stacks.append([])
			self.stack_used.append(self.stack_num)
			self.stack_num += 1
		return

	def pop(self) -> int:
		i = self.stack_num - 1
		if len(self.stacks[i]) == 0:
			if i == 0:
				return -1
			self.stacks.pop()
			self.stack_used.pop()
			self.stack_num -= 1
			i = self.stack_num - 1
		val = self.stacks[i].pop()
		if len(self.stack_used) == 0 or self.stack_used[-1] != i:
			self.stack_used.append(i)
		self.cleanEmptyTail()
		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
			if mid_index > index:
				end = i
			else:
				head = i
		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()
		self.insertUsed(index)
		self.cleanEmptyTail()
		return val


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)


class DinnerPlates:

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

	def push(self, val: int) -> None:
		while self.cl < len(self.s) and len(self.s[self.cl]) == self.c:
			self.cl += 1
		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


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
		heapq.heappush(self.indices, index)
		return self.arr[index].pop()


class DinnerPlates:

	def __init__(self, capacity: int):
		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


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


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


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)


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


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([])
			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


class DinnerPlates:

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

	def push(self, val: int) -> None:
		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:
		if 0 <= index < len(self.s) and self.s[index]:
			heapq.heappush(self.h, index)
			return self.s[index].pop()
		return -1


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:
		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])
			elif self.q[index]:
				self.q[index] += [val]
			else:
				self.q[index] = [val]
		elif self.q and self.q[-1] and (len(self.q[-1]) < self.c):
			self.q[-1] += [val]
		else:
			self.q.append([val])

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

	def popAtStack(self, index: int) -> int:
		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