class Deq( object ):
	def __init__(self, size=64):
		self._size = size + 1
		self.deq = [None for _ in xrange(self._size)]
		self.head = self._size - 1
		self.tail = 0

	def size(self):
		return self._size - 1

	def __getitem__(self, idx):
		return self.deq[idx]

	def __setitem__(self, idx, val):
		self.deq[idx] = val

	def pop(self):
		tail = (self.tail - 1) % self._size
		val, self.tail = self._pop(tail, self.head, self.tail)
		return val

	def poph(self):
		head = (self.head + 1) % self._size
		val, self.head = self._pop(head, self.tail, self.head)
		return val

	def _pop(self, new, check, old):
		try:
			assert (new != check)
			return self[new], new
		except:
			return None, old

	def check(fn):
		def _checksize(self, val):
			try:
				assert(self.head != self.tail)
			except:
				self._refresh(self._resize(self.size()))

			return fn(self, val)

		return _checksize

	@check
	def push(self, val):
		self[self.tail] = val
		self.tail = (self.tail + 1) % self._size

	@check
	def pushh(self, val):
		self[self.head] = val
		self.head = (self.head - 1) % self._size


	def _resize(self, size):
		deq = Deq(2*size)
		val = self.poph()

		while val != None:
			deq.push(val)
			val = self.poph()

		return deq

	def _refresh(self, deq):
		self._size = deq._size
		self.head  = deq.head
		self.tail  = deq.tail
		self.deq = deq.deq