function deque()
	local cap = 5
	local elems = {}
	for i = 0, cap - 1 do
		elems[i] = nil
	end
	return {
		start = 0,
		size = 0,
		cap = cap,
		elems = elems,
		pprint = pprint,
		pop = pop,
		prepend = prepend,
		append = append,
		popleft = popleft,
		get = get,
		set = set,
	}
end

function pprint(self)
	io.write(self.start .. "->" .. self.size .. ": ")
	local i = self.start
	for i = 0, self.cap - 1 do
		io.write((self.elems[i] or "_") .. " ")
	end
	io.write("\n")
end

local function extend(self)
	local copy = {}
	for i = 0, self.size - 1 do
		copy[i] = self.elems[(self.start + i) % self.size]
	end
	for i = self.size, 2 * self.size - 1 do
		copy[i] = nil
	end
	self.elems = copy
	self.start = 0
	self.cap = self.cap * 2
end

function append(self, n)
	if self.size == self.cap then
		extend(self)
	end
	self.elems[(self.start + self.size) % self.cap] = n
	self.size = self.size + 1
end

function pop(self)
	if self.size > 0 then
		local i = (self.start + self.size - 1) % self.cap
		local v = self.elems[i]
		self.elems[i] = nil
		self.size = self.size - 1
		return v
	else
		return nil
	end
end

function prepend(self, n)
	if self.size == self.cap then
		extend(self)
	end
	self.size = self.size + 1
	self.start = (self.start + self.cap - 1) % self.cap
	self.elems[self.start] = n
end

function popleft(self)
	if self.size > 0 then
		local v = self.elems[self.start]
		self.elems[self.start] = nil
		self.start = (self.start + 1) % self.cap
		self.size = self.size - 1
		return v
	else
		return nil
	end
end

function get(self, i)
	if 0 <= i and i < self.size then
		return self.elems[(self.start + i) % self.cap]
	else
		return nil
	end
end

function set(self, i, n)
	if 0 <= i and i < self.size then
		self.elems[(self.start + i) % self.cap] = n
	end
end