A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed.

A basic queue has the following operations:

Enqueue: add a new element to the end of the queue.
Dequeue: remove the element from the front of the queue and return it.

In this challenge, you must first implement a queue using two stacks. Then process $\textit{q}$ queries, where each query is one of the following $3$ types: 

1 x: Enqueue element $\boldsymbol{x}$ into the end of the queue.
2: Dequeue the element at the front of the queue.
3: Print the element at the front of the queue.

Input Format

The first line contains a single integer, $\textit{q}$, denoting the number of queries. 

Each line $\boldsymbol{i}$ of the $\textit{q}$ subsequent lines contains a single query in the form described in the problem statement above. All three queries start with an integer denoting the query $\textit{type}$, but only query $1$ is followed by an additional space-separated value, $\boldsymbol{x}$, denoting the value to be enqueued.

Constraints

$1\leq q\leq10^5$  
$1\leq type\leq3$  
$1\leq|x|\leq10^9$  
It is guaranteed that a valid answer always exists for each query of type $3$.

Output Format

For each query of type $3$, print the value of the element at the front of the queue on a new line. 

Sample Input
STDIN   Function
-----   --------
10      q = 10 (number of queries)
1 42    1st query, enqueue 42
2       dequeue front element
1 14    enqueue 42
3       print the front element
1 28    enqueue 28
3       print the front element
1 60    enqueue 60
1 78    enqueue 78
2       dequeue front element
2       dequeue front element

Sample Output
14
14

Explanation

Perform the following sequence of actions:

Enqueue $\textbf{42}$; $\textit{queue}=\{42\}$.
Dequeue the value at the head of the queue, $\textbf{42}$; $\mbox{queue}=\{\}$.
Enqueue $\mathbf{14}$; $\textit{queue}=\{14\}$.
Print the value at the head of the queue, $\mathbf{14}$; $\textit{queue}=\{14\}$.
Enqueue $28$; $queue=\{14,28\}$.
Print the value at the head of the queue, $\mathbf{14}$; $queue=\{14,28\}$.
Enqueue $\mbox{60}$; $queue=\{14,28,60\}$.
Enqueue $78$; $queue=\{14,28,60,78\}$.
Dequeue the value at the head of the queue, $\mathbf{14}$; $queue=\{28,60,78\}$.
Dequeue the value at the head of the queue, $28$; $queue=\{60,78\}$.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
n = int(input())
q = []
for i in range(n):
	query = [int(i) for i in input().split()]
	if query[0] == 1:
		q.append(query[1])
	if query[0] == 2:
		q.pop(0)
	if query[0] == 3:
		print(q[0])


l = []
for i in range(int(input())):
	inp = [int(x) for x in input().split()]
	if inp[0] == 1:
		l.append(inp[1])
	elif inp[0] == 2:
		l.pop(0)
	else:
		print(l[0])


class Node(object):

	def __init__(self):
		self.val = -1
		self.next = None

class stack(object):

	def __init__(self):
		super().__init__()
		self.first = None
		self.no_of_items = 0

	def isEmpty(self):
		return self.first == None

	def push(self, val):
		oldfirst = self.first
		self.first = Node()
		self.first.val = val
		self.first.next = oldfirst

	def pop(self):
		if self.first == None:
			return None
		val = self.first.val
		self.first = self.first.next
		return val

	def peek(self):
		return self.first.val

class queue(object):

	def __init__(self):
		super().__init__()
		self.s1 = stack()
		self.s2 = stack()

	def push(self, a):
		self.s1.push(a)

	def pop(self):
		if self.s1.isEmpty():
			return self.s2.pop()
		elif not self.s2.isEmpty():
			return self.s2.pop()
		else:
			while True:
				a = self.s1.pop()
				if self.s1.isEmpty():
					break
				self.s2.push(a)
			return a

	def peek(self):
		if not self.s2.isEmpty():
			return self.s2.peek()
		while not self.s1.isEmpty():
			self.s2.push(self.s1.pop())
		return self.s2.peek()
N = int(input().strip())
q1 = queue()
for i in range(N):
	ln = input().strip().split()
	if ln[0] == '1':
		q1.push(int(ln[1]))
	elif ln[0] == '2':
		q1.pop()
	elif ln[0] == '3':
		print(q1.peek())


queriesNum = int(input().strip())
stack1 = []
stack2 = []
for i in range(queriesNum):
	query = input().split(' ')
	if query[0] == '2':
		if stack2:
			stack2.pop()
		else:
			stack2 = stack1[1:]
			stack2.reverse()
			stack1 = []
	elif query[0] == '3':
		top = None
		if stack2:
			top = stack2.pop()
		else:
			stack2 = stack1[1:]
			stack2.reverse()
			top = stack1[0]
			stack1 = []
		print(str(top))
		stack2.append(top)
	elif query[0] == '1':
		if stack2:
			stack1 = stack2
			stack1.reverse()
			stack2 = []
		item = query[1]
		stack1.append(int(item))


class Stack:

	def __init__(self):
		self.__stack = []

	def Push(self, x):
		self.__stack += [x]

	def Pop(self):
		self.__stack = self.__stack[:-1]
	Empty = lambda self: not len(self.__stack)
	Top = lambda self: None if self.Empty() else self.__stack[-1]
(stack1, stack2) = (Stack(), Stack())
for _ in range(int(input())):
	command = list(map(int, input().split()))
	if command[0] == 1:
		stack1.Push(command[1])
	else:
		if stack2.Empty():
			while not stack1.Empty():
				stack2.Push(stack1.Top())
				stack1.Pop()
		if command[0] == 2:
			stack2.Pop()
		else:
			print(stack2.Top())


q = int(input())
qa = []
for q0 in range(q):
	li = [int(i) for i in input().strip().split()]
	if li[0] == 1:
		qa.append(li[1])
	elif li[0] == 2:
		del qa[0]
	else:
		print(qa[0])


query_cnt = int(input())
queue_stack = []
dequeue_stack = []
for cnt in range(query_cnt):
	query = [int(x) for x in input().split(' ')]
	if query[0] == 1:
		queue_stack.append(query[1])
	if query[0] == 2:
		if len(dequeue_stack) == 0:
			while len(queue_stack) != 0:
				dequeue_stack.append(queue_stack[-1])
				queue_stack = queue_stack[:-1]
		dequeue_stack = dequeue_stack[:-1]
	if query[0] == 3:
		if len(dequeue_stack) == 0:
			while len(queue_stack) != 0:
				dequeue_stack.append(queue_stack[-1])
				queue_stack = queue_stack[:-1]
		print(dequeue_stack[-1])


queue = []
for _ in range(int(input())):
	command = input()
	if command.startswith('1'):
		queue.append(command.split()[-1])
	elif command.startswith('2'):
		if len(queue) > 0:
			queue.pop(0)
	elif command.startswith('3'):
		print(queue[0])


class myQueue:

	def __init__(self):
		self.q1 = []
		self.q2 = []

	def push(self, item):
		self.q1.append(item)

	def pop(self):
		if len(self.q2) == 0:
			while len(self.q1) > 0:
				self.q2.append(self.q1.pop())
		return self.q2.pop()

	def peek(self):
		if len(self.q2) == 0:
			while len(self.q1) > 0:
				self.q2.append(self.q1.pop())
		print(self.q2[len(self.q2) - 1])
myQ = myQueue()
n = int(input())
for i in range(n):
	line = input().split(' ')
	if int(line[0]) == 1:
		myQ.push(int(line[1]))
	elif int(line[0]) == 2:
		myQ.pop()
	elif int(line[0]) == 3:
		myQ.peek()


n = int(input())
arr = []
for i in range(n):
	tem = [int(i) for i in input().split()]
	if tem[0] == 1:
		arr.append(tem[1])
	elif tem[0] == 2:
		arr.pop(0)
	else:
		print(arr[0])


class MyQueue:

	def __init__(self):
		self.stk1 = []
		self.stk2 = []

	def _flip(self):
		if len(self.stk2) == 0 and len(self.stk1) > 0:
			self.stk2 = list(reversed(self.stk1))
			self.stk1 = []
		return

	def enqueue(self, v):
		self.stk1.append(v)
		return

	def dequeue(self):
		self._flip()
		if len(self.stk2) > 0:
			self.stk2.pop()
		return

	def front(self):
		self._flip()
		if len(self.stk2) > 0:
			return self.stk2[-1]
		else:
			return None

def read_input():
	Q = int(input().strip())
	mq = MyQueue()
	for i in range(Q):
		ln = [int(x) for x in input().strip().split()]
		if ln[0] == 1:
			mq.enqueue(ln[1])
		elif ln[0] == 2:
			mq.dequeue()
		elif ln[0] == 3:
			print(mq.front())
read_input()


import sys

class Queue(object):

	def __init__(self):
		self.data = []

	def enqueue(self, val):
		self.data.append(val)

	def dequeue(self):
		return self.data.pop(0)

	def head(self):
		return self.data[0]
q = Queue()
data = sys.stdin.readlines()
num = int(data.pop(0))
while data:
	query = data.pop(0).split(' ')
	action = query[0]
	if int(action[0]) == 1:
		q.enqueue(int(query[1]))
	elif int(action[0]) == 2:
		q.dequeue()
	else:
		print(q.head())


import sys
q1 = []
q2 = []
t = int(input().strip())
for a0 in range(t):
	s = input().strip()
	if s[0] == '1':
		q1.append(s[2:])
	if s == '2':
		if not q2:
			while q1:
				q2.append(q1.pop())
		q2.pop()
	if s == '3':
		if q2:
			hey = q2.pop()
			print(hey)
			q2.append(hey)
		else:
			print(q1[0])


num_statements = int(input())
in_stack = []
out_stack = []
for i in range(num_statements):
	command = list(map(lambda x: int(x), input().split(' ')))
	if command[0] == 1:
		in_stack.append(command[1])
	elif command[0] == 2:
		if out_stack:
			out_stack.pop()
		else:
			for i in range(len(in_stack)):
				value = in_stack.pop()
				out_stack.append(value)
			out_stack.pop()
	elif command[0] == 3:
		if out_stack:
			print(out_stack[-1])
		else:
			for i in range(len(in_stack)):
				value = in_stack.pop()
				out_stack.append(value)
			print(out_stack[-1])


s1 = []
s2 = []
q = s1
for _ in range(int(input())):
	query = [int(x) for x in input().split()]
	if len(query) == 2:
		q.append(query[1])
	elif query[0] == 2:
		q.pop(0)
	else:
		print(q[0])


class Node(object):

	def __init__(self, data=None, next=None):
		self.data = data
		self.next = next

class Stack(object):

	def __init__(self):
		self.size = 0
		self.head = None

	def push(self, val):
		self.size += 1
		if self.head is None:
			self.head = Node(val)
		else:
			self.head = Node(val, self.head)

	def pop(self):
		if self.head is not None:
			return_val = self.head.data
			self.head = self.head.next
			self.size -= 1
			return return_val

	def isEmpty(self):
		return self.size == 0

	def peek(self):
		if self.head:
			return self.head.data

class Queue(object):

	def __init__(self):
		self.stack = Stack()
		self.queue = Stack()

	def enqueue(self, data):
		self.queue.push(data)

	def dequeue(self):
		if self.stack.isEmpty():
			while not self.queue.isEmpty():
				self.stack.push(self.queue.pop())
		return self.stack.pop()

	def top(self):
		if self.stack.isEmpty():
			while not self.queue.isEmpty():
				self.stack.push(self.queue.pop())
		return self.stack.peek()
num_queries = int(input())
queue = Queue()
for _ in range(num_queries):
	query = input().split(' ')
	if query[0] == '1':
		queue.enqueue(query[1])
	elif query[0] == '2':
		queue.dequeue()
	else:
		print(queue.top())


from collections import deque
n = int(input())
queue = deque()
for _ in range(n):
	query = list(map(int, input().strip().split()))
	if query[0] == 1:
		queue.append(query[1])
	if query[0] == 2:
		queue.popleft()
	if query[0] == 3:
		print(queue[0])


queue = []

def enq(v):
	queue.append(v)

def deq():
	queue.pop(0)

def peek():
	return queue[0]
q = int(input().strip())
for i in range(q):
	line = input().strip()
	op = line[0]
	if op == '1':
		x = int(line[1:].strip())
		enq(x)
	elif op == '2':
		deq()
	elif op == '3':
		print(peek())


class Node:

	def __init__(self, data, next=None):
		self.data = data
		self.next = next

	def __str__(self):
		return str(self.data) + (' -> ' + str(self.next) if self.next is not None else '')
head = None
tail = None
q = int(input())
for _ in range(q):
	line = list(map(int, input().split()))
	(f, x) = (line[0], None)
	if f == 1:
		x = line[1]
		if head is None and tail is None:
			head = tail = Node(x)
		else:
			tail.next = Node(x)
			tail = tail.next
	elif f == 2:
		if tail == head:
			head = tail = None
		else:
			head = head.next
	elif f == 3:
		print(head.data)


N = int(input())
que = []
for i in range(N):
	query = input().split()
	if len(query) == 2:
		que.append(int(query[1]))
	elif query[0] == '2':
		que.pop(0)
	else:
		print(que[0])


from collections import deque
n = int(input())
queue = deque()
for _ in range(n):
	query = list(map(int, input().strip().split()))
	if query[0] == 1:
		queue.append(query[1])
	if query[0] == 2:
		queue.popleft()
	if query[0] == 3:
		print(queue[0])


from collections import deque
n = int(input())
queue = deque()
for _ in range(n):
	query = list(map(int, input().strip().split()))
	if query[0] == 1:
		queue.append(query[1])
	if query[0] == 2:
		queue.popleft()
	if query[0] == 3:
		print(queue[0])


(a, b) = ([], [])
q = int(input())
for _ in range(q):
	(c, *val) = [int(x) for x in input().split()]
	if c == 1:
		b.append(val[0])
	else:
		if not a:
			while b:
				a.append(b.pop())
		if c == 2:
			a.pop()
		elif c == 3:
			print(a[-1])


q = int(input())
queue = []
for a in range(q):
	query = [int(x) for x in input().strip().split()]
	if query[0] == 1:
		queue.insert(0, query[1])
	elif query[0] == 2:
		queue.pop()
	else:
		print(queue[-1])


from collections import deque
n = int(input())
queue = deque()
for _ in range(n):
	query = list(map(int, input().strip().split()))
	if query[0] == 1:
		queue.append(query[1])
	if query[0] == 2:
		queue.popleft()
	if query[0] == 3:
		print(queue[0])


n = int(input())
queries = []
for _ in range(n):
	data = input().split()
	if len(data) == 2:
		(q, val) = [int(val) for val in data]
	else:
		(q, val) = (int(data[0]), None)
	queries.append((q, val))

class Queue:

	def __init__(self):
		self.front = []
		self.back = []

	def enqueue(self, item):
		self.back.append(item)

	def dequeue(self):
		if not self.front:
			self.front.extend(self.back[::-1])
			self.back = []
		return self.front.pop()

	def print_front(self):
		if not self.front:
			print(self.back[0])
		else:
			print(self.front[-1])
queue = Queue()
for (q, val) in queries:
	if q == 1:
		queue.enqueue(val)
	elif q == 2:
		queue.dequeue()
	else:
		queue.print_front()


from collections import deque
n = int(input())
queue = deque()
for _ in range(n):
	query = list(map(int, input().strip().split()))
	if query[0] == 1:
		queue.append(query[1])
	if query[0] == 2:
		queue.popleft()
	if query[0] == 3:
		print(queue[0])


N = int(input())
queue = []
for i in range(N):
	line = input().split()
	command = line[0]
	if command == '1':
		queue.append(line[1])
	elif command == '2':
		queue = queue[1:]
	elif command == '3':
		print(queue[0])


import sys

class Queue(object):

	def __init__(self):
		self.items = []

	def enqueue(self, item):
		self.items.append(item)

	def deque(self):
		self.items.pop(0)

	def front(self):
		return self.items[0]

	def size(self):
		return len(self.items)

	def is_empty(self):
		return self.items == []
q = Queue()
for _ in range(int(input().strip())):
	type_list = input().split(' ')
	if type_list[0] == '1':
		q.enqueue(int(type_list[1]))
	elif type_list[0] == '2':
		q.deque()
	elif type_list[0] == '3':
		print(q.front())


from collections import deque
n = int(input())
queue = deque()
for _ in range(n):
	query = list(map(int, input().strip().split()))
	if query[0] == 1:
		queue.append(query[1])
	if query[0] == 2:
		queue.popleft()
	if query[0] == 3:
		print(queue[0])


class Queue:

	def __init__(self):
		self.inbox = []
		self.outbox = []

	def queue(self, val):
		self.inbox.append(val)

	def dequeue(self):
		if not self.outbox:
			while self.inbox:
				self.outbox.append(self.inbox.pop())
		return self.outbox.pop()

	def peekFront(self):
		if self.outbox:
			return self.outbox[-1]
		if self.inbox:
			return self.inbox[0]
queue = Queue()
num_queries = int(input().strip())
for _ in range(num_queries):
	op = list(map(int, input().strip().split(' ')))
	if op[0] == 1:
		queue.queue(op[1])
	elif op[0] == 2:
		queue.dequeue()
	else:
		print(queue.peekFront())


q = int(input().strip())
queue = []
for _ in range(q):
	query = [int(i) for i in input().strip().split()]
	if query[0] == 1:
		queue.append(query[1])
	elif query[0] == 2:
		queue.pop(0)
	elif query[0] == 3:
		print(queue[0])


class Queue(object):

	def __init__(self):
		self.data = []

	def enqueue(self, dat):
		self.data.append(dat)

	def dequeue(self):
		return self.data.pop(0)

	def peek(self):
		return self.data[0]
queue = Queue()
N = int(input())
for _ in range(N):
	x = input()
	if x[0] == '1':
		queue.enqueue([int(i) for i in x.split()][1])
	elif x[0] == '2':
		queue.dequeue()
	elif x[0] == '3':
		print(queue.peek())


from collections import deque
n = int(input())
queue = deque()
for _ in range(n):
	query = list(map(int, input().strip().split()))
	if query[0] == 1:
		queue.append(query[1])
	if query[0] == 2:
		queue.popleft()
	if query[0] == 3:
		print(queue[0])


from collections import deque
q = int(input())
queue = deque()
for _ in range(q):
	queries = list(map(int, input().split()))
	if len(queries) > 1:
		queue.append(queries[1])
	elif queries[0] == 2:
		queue.popleft()
	elif queries[0] == 3:
		print(queue[0])


def read():
	return [int(v) for v in input().split()]
n = int(input())
queue = []
for query in [read() for _ in range(n)]:
	if query[0] == 1:
		queue.append(query[1])
	elif query[0] == 2:
		queue.pop(0)
	else:
		print(queue[0])


inbox = []
outbox = []
q = int(input())
for i in range(q):
	query = input()
	if query[0] == '1':
		inbox.append(query[2:])
	elif query[0] == '2':
		outbox.append(inbox.pop(0))
	else:
		print(inbox[0])


from collections import deque
queue = deque()
for _ in range(int(input())):
	s = input()
	if s == '3':
		print(queue[0])
	elif s == '2':
		queue.popleft()
	else:
		(_, data) = s.split()
		queue.append(data)


q = int(input())
_type = 0
value = 0
input_stack = []
output_stack = []
for i in range(q):
	input_data = [int(data) for data in input().strip().split()]
	_type = input_data[0]
	if len(input_data) == 2:
		value = input_data[1]
	if _type == 1:
		input_stack.append(value)
	elif _type == 2:
		input_stack.reverse()
		output_stack = input_stack
		output_stack.pop()
		output_stack.reverse()
		input_stack = output_stack
	elif _type == 3:
		print(input_stack[0])


n = int(input())
q = []
for i in range(n):
	inp = input().strip().split()
	if int(inp[0]) == 1:
		q.append(int(inp[1]))
	elif int(inp[0]) == 2:
		q.pop(0)
	elif int(int(inp[0])) == 3:
		print(q[0])


from collections import deque
n = int(input())
queue = deque()
for _ in range(n):
	query = list(map(int, input().strip().split()))
	if query[0] == 1:
		queue.append(query[1])
	if query[0] == 2:
		queue.popleft()
	if query[0] == 3:
		print(queue[0])


class Stack:

	def __init__(self):
		self.stack = []

	def __str__(self):
		return str(self.stack)

	def __len__(self):
		return len(self.stack)

	def peek(self):
		return self.stack[len(self.stack) - 1]

	def pop(self):
		return self.stack.pop()

	def push(self, x):
		self.stack.append(x)

	def swap(self, stack):
		for i in range(len(self.stack)):
			stack.push(self.stack.pop())
s1 = Stack()
s2 = Stack()
T = int(input())
for t in range(T):
	q = list(map(int, input().split(' ')))
	if q[0] == 1:
		s1.push(q[1])
	elif q[0] == 2:
		if len(s2) == 0:
			s1.swap(s2)
		s2.pop()
	else:
		if len(s2) == 0:
			s1.swap(s2)
		print(s2.peek())


N = int(input())
l = []
for i in range(N):
	num = list(map(int, input().split()))
	if num[0] == 1:
		l.insert(0, num[1])
	elif num[0] == 2:
		l.pop()
	elif num[0] == 3:
		print(l[-1])
	else:
		print('0')


Q = int(input())
stack1 = []
stack2 = []

def debug(stack):
	if not len(stack):
		print('this stack is empty')
	for i in stack:
		print(i, end=' ')

def _is_empty(stack):
	if not len(stack):
		return True
	return False

def enque(element):
	stack1.append(element)

def deque():
	if _is_empty(stack2):
		while not _is_empty(stack1):
			stack2.append(stack1.pop())
	return stack2.pop()

def print_func():
	element = deque()
	print(element)
	stack2.append(element)
for i in range(Q):
	line = input().split()
	cmd = int(line[0])
	if cmd == 1:
		element = int(line[1])
		enque(element)
	elif cmd == 2:
		deque()
	elif cmd == 3:
		print_func()


from collections import deque
inbox = deque()
outbox = deque()
for _ in range(int(input())):
	q = [int(i) for i in input().split()]
	if q[0] == 1:
		inbox.append(q[1])
	else:
		if not outbox:
			while inbox:
				outbox.append(inbox.pop())
		val = outbox.pop()
		if q[0] == 3:
			print(val)
			outbox.append(val)


from collections import deque
queue = deque([])
userIn = input()
for i in range(int(userIn)):
	query = input().split()
	if int(query[0]) == 1:
		queue.append(query[1])
	elif int(query[0]) == 2:
		queue.popleft()
	else:
		print(queue[0])


(s1, s2) = ([], [])
for _ in range(int(input())):
	q = input().split()
	if q[0] == '1':
		s1.append(q[1])
	elif q[0] == '2':
		if len(s2) == 0:
			while len(s1):
				s2.append(s1.pop())
		s2.pop()
	elif q[0] == '3':
		if len(s2) == 0:
			while len(s1):
				s2.append(s1.pop())
		print(s2[-1])


stack_1 = []
stack_2 = []
l = int(input())
for i in range(0, l):
	q = input().split()
	if q[0] == '1':
		stack_1.append(q[1])
	elif q[0] == '2':
		if len(stack_2) == 0:
			while len(stack_1):
				stack_2.append(stack_1.pop())
		stack_2.pop()
	elif q[0] == '3':
		if not stack_2:
			while len(stack_1):
				stack_2.append(stack_1.pop())
		print(stack_2[-1])


import sys

def removeQueue(stack):
	second = []
	while stack:
		second.append(stack.pop())
	second.pop()
	while second:
		stack.append(second.pop())
	return stack

def printQueue(stack):
	second = []
	while stack:
		second.append(stack.pop())
	temp = second.pop()
	print(temp)
	second.append(temp)
	while second:
		stack.append(second.pop())
	return stack
stack = []
for i in sys.stdin.readlines()[1:]:
	string = i.strip().split()
	if len(string) > 1:
		stack.append(string[1])
	elif string[0] is '2':
		stack.pop(0)
	else:
		print(stack[0])


n = int(input())
stack = []
for _ in range(n):
	x = input().split()
	if x[0] == '1':
		stack.append(x[1])
	elif x[0] == '2':
		del stack[0]
	elif x[0] == '3':
		print(stack[0])


n = int(input())
s1 = []
s2 = []
for _ in range(n):
	x = input().split()
	if x[0] == '1':
		s1.append(x[1])
	elif x[0] == '2':
		if s2 == []:
			while len(s1):
				s2.append(s1.pop())
		s2.pop()
	elif x[0] == '3':
		if s2 == []:
			while len(s1):
				s2.append(s1.pop())
		print(s2[-1])


class Queue(object):

	def __init__(self):
		self.old = []
		self.new = []

	def enqueue(self, value):
		self.new.append(value)

	def dequeue(self):
		if self.old:
			self.old.pop()
		else:
			while self.new:
				self.old.append(self.new.pop())
			self.old.pop()

	def peek(self):
		if self.old:
			return self.old[-1]
		else:
			return self.new[0]
q = Queue()
for line in range(int(input())):
	values = list(map(int, input().split()))
	if values[0] == 1:
		q.enqueue(values[1])
	elif values[0] == 2:
		q.dequeue()
	else:
		print(q.peek())


(old, new) = ([], [])
for _ in range(int(input())):
	val = list(map(int, input().split()))
	if val[0] == 1:
		new.append(val[1])
	elif val[0] == 2:
		if not old:
			while new:
				old.append(new.pop())
		old.pop()
	else:
		print(old[-1] if old else new[0])


(old, new) = ([], [])
for _ in range(int(input())):
	val = list(map(int, input().split()))
	if val[0] == 1:
		new.append(val[1])
	elif val[0] == 2:
		if not old:
			while new:
				old.append(new.pop())
		old.pop()
	else:
		print(old[-1] if old else new[0])


stack1 = []
stack2 = []

def refill():
	if len(stack1) == 0:
		while len(stack2) != 0:
			e = stack2.pop()
			stack1.append(e)
num_queries = int(input())
for i in range(0, num_queries):
	query = list(map(lambda x: int(x), input().split()))
	op = query[0]
	if op == 1:
		stack2.append(query[1])
	elif op == 2:
		refill()
		stack1.pop()
	elif op == 3:
		refill()
		x = stack1.pop()
		print(x)
		stack1.append(x)


from collections import deque
q = deque()
Q = int(input().strip())
for _ in range(Q):
	line = input().strip()
	if line == '2':
		q.popleft()
	elif line == '3':
		print(q[0])
	else:
		(_, x) = list(map(int, line.split(' ')))
		q.append(x)


class Stack(object):

	def __init__(self):
		self.data = []

	def push(self, newData):
		self.data.append(newData)

	def pop(self):
		if not self.data:
			return None
		topData = self.data[-1]
		del self.data[-1]
		return topData

	def peak(self):
		if not self.data:
			return None
		return self.data[-1]

class duoQueue(object):

	def __init__(self):
		self.inputStack = Stack()
		self.outputStack = Stack()

	def enqueue(self, newData):
		self.inputStack.push(newData)

	def dequeue(self):
		if self.outputStack.peak():
			outputData = self.outputStack.pop()
			return
		while self.inputStack.peak():
			self.outputStack.push(self.inputStack.pop())
		outputData = self.outputStack.pop()
		return

	def peak(self):
		if self.outputStack.peak():
			outputData = self.outputStack.peak()
			return outputData
		while self.inputStack.peak():
			self.outputStack.push(self.inputStack.pop())
		outputData = self.outputStack.peak()
		return outputData
numQueries = int(input())
myQueue = duoQueue()
for i in range(0, numQueries):
	query = [int(i) for i in input().split()]
	if query[0] == 1:
		myQueue.enqueue(query[1])
	elif query[0] == 2:
		myQueue.dequeue()
	elif query[0] == 3:
		print(myQueue.peak())


(old, new) = ([], [])
for _ in range(int(input())):
	val = list(map(int, input().split()))
	if val[0] == 1:
		if not new:
			first = val[1]
		new.append(val[1])
	elif val[0] == 2:
		if not old:
			while new:
				old.append(new.pop())
		old.pop()
	else:
		print(old[-1] if old else first)


from collections import deque
n = int(input())
d = deque()
for i in range(n):
	x = list(map(int, input().split()))
	if x[0] == 1:
		d.append(x[1])
	if x[0] == 2:
		d.popleft()
	if x[0] == 3:
		print(d[0])


n = int(input())
queue = []
for i in range(n):
	query = input().split(' ')
	if query[0] == '1':
		queue.append(query[1])
	if query[0] == '2':
		if len(queue) > 0:
			queue.pop(0)
	if query[0] == '3':
		print(queue[0])


class Queue:

	def __init__(self):
		self.back = []
		self.front = []

	def append(self, x):
		self.back.append(x)

	def pop(self):
		if not self.front:
			self.front = self.back[::-1]
			self.back = []
		return self.front.pop()

	def peek(self):
		if not self.front:
			self.front = self.back[::-1]
			self.back = []
		return self.front[-1]
queue = Queue()
Q = int(input())
for _ in range(Q):
	q = input()
	if q[0] == '1':
		queue.append(int(q[2:]))
	elif q[0] == '2':
		queue.pop()
	else:
		print(queue.peek())


class Queue:

	def __init__(self):
		self.inbox = []
		self.outbox = []

	def enqueue(self, item):
		self.inbox.append(item)

	def dequeue(self):
		self.front()
		return self.outbox.pop()

	def front(self):
		if len(self.outbox) == 0:
			while len(self.inbox):
				self.outbox.append(self.inbox.pop())
		return self.outbox[-1]
q = int(input())
Q = Queue()
for _ in range(q):
	line = input()
	if line[0] == '1':
		Q.enqueue(int(line.split()[1]))
	elif line[0] == '2':
		Q.dequeue()
	else:
		print(Q.front())


import sys

class queue:

	def __init__(self):
		self.data = []

	def enqueue(self, item):
		self.data.append(item)

	def dequeue(self):
		value = self.data[0]
		if len(self.data) == 1:
			self.data = []
		else:
			self.data = self.data[1:]
		return value

	def print_item(self):
		print(self.data[0])
Q = queue()
j = int(sys.stdin.readline())
for i in range(0, j):
	Line = sys.stdin.readline()
	L = map(int, Line.strip().split(' '))
	L = list(L)
	if L[0] == 1:
		Q.enqueue(L[1])
	elif L[0] == 2:
		Q.dequeue()
	elif L[0] == 3:
		Q.print_item()


q = int(input())

class jQueue:

	def __init__(self):
		self.sIn = []
		self.sOut = []

	def enQ(self, x):
		self.sIn.append(x)

	def flip(self):
		if len(self.sOut) == 0:
			self.sOut = list(reversed(self.sIn))
			self.sIn = []

	def deQ(self):
		self.flip()
		self.sOut.pop()

	def printHead(self):
		self.flip()
		print(self.sOut[len(self.sOut) - 1])
jq = jQueue()
for i in range(q):
	command = list(map(int, input().split(' ')))
	qType = command[0]
	if qType == 1:
		jq.enQ(command[1])
	elif qType == 2:
		jq.deQ()
	else:
		jq.printHead()


queue = []
n = int(input().strip())
index = 0
for i in range(n):
	temp = [int(a) for a in input().strip().split(' ')]
	if temp[0] == 1:
		queue.append(temp[1])
	elif temp[0] == 2:
		index += 1
	else:
		print(queue[index])


class MyQueue(object):

	def __init__(self):
		self.queue = []

	def peek(self):
		return self.queue[0]

	def dequeue(self):
		self.queue.pop(0)

	def put(self, value):
		self.queue.append(value)
queue = MyQueue()
t = int(input())
for line in range(t):
	values = map(int, input().split())
	values = list(values)
	if values[0] == 1:
		queue.put(values[1])
	elif values[0] == 2:
		queue.dequeue()
	else:
		print(queue.peek())


from collections import deque

class Q:

	def __init__(self):
		(self.s1, self.s2) = (deque(), deque())

	def enqueue(self, item):
		self.s1.append(item)

	def dequeue(self):
		if not self.s2:
			self._reload()
		return self.s2.pop()

	def _reload(self):
		while self.s1:
			self.s2.append(self.s1.pop())

	@property
	def front(self):
		if not self.s2:
			self._reload()
		return self.s2[-1]
q = Q()
n = int(input())
for _ in range(n):
	query = input().split()
	if len(query) == 2:
		q.enqueue(int(query[1]))
	elif query[0] == '2':
		q.dequeue()
	elif query[0] == '3':
		print(q.front)


class Stack:

	def __init__(self):
		self.items = []

	def isEmpty(self):
		return self.items == []

	def push(self, item):
		self.items.append(item)

	def pop(self):
		return self.items.pop()

	def peek(self):
		return self.items[len(self.items) - 1]

	def size(self):
		return len(self.items)

class Queue:

	def __init__(self):
		self.inbox = Stack()
		self.outbox = Stack()

	def enqueue(self, item):
		self.inbox.push(item)

	def dequeue(self):
		if not self.outbox.isEmpty():
			return self.outbox.pop()
		else:
			self.__populateOutbox()
			return self.outbox.pop()

	def peek(self):
		if self.outbox.isEmpty():
			self.__populateOutbox()
		return self.outbox.peek()

	def __populateOutbox(self):
		while not self.inbox.isEmpty():
			self.outbox.push(self.inbox.pop())
queue = Queue()
for q in range(int(input())):
	inp = input()
	if inp.startswith('1'):
		queue.enqueue(inp.split()[1])
	elif inp.startswith('2'):
		queue.dequeue()
	else:
		print(queue.peek())


(old, new) = ([], [])
for _ in range(int(input())):
	val = list(map(int, input().split()))
	if val[0] == 1:
		new.append(val[1])
	elif val[0] == 2:
		if not old:
			while new:
				old.append(new.pop())
		old.pop()
	else:
		print(old[-1] if old else new[0])


Q = int(input())
s1 = list()
s2 = list()
prev = '1'
for q in range(Q):
	query = input().split(' ')
	if query[0] == '1':
		s1.append(query[1])
	elif query[0] == '2':
		if len(s2) == 0:
			while len(s1) != 0:
				s2.append(s1[-1])
				s1.pop()
		s2.pop()
	elif query[0] == '3':
		if len(s2) == 0:
			while len(s1) != 0:
				s2.append(s1[-1])
				s1.pop()
		print(s2[-1])
	else:
		assert false
	prev = query[0]


from collections import deque
import sys
queries = int(sys.stdin.readline().strip())
queue = deque()
for i in range(queries):
	command = sys.stdin.readline().strip().split()
	op = int(command[0])
	if op == 1:
		queue.append(int(command[1]))
	elif op == 2:
		queue.popleft()
	else:
		print(queue[0])


import sys

class Queue:

	def __init__(self):
		self.inStack = list()
		self.outStack = list()

	def enqueue(self, item):
		self.inStack.append(item)

	def dequeue(self):
		if len(self.outStack) != 0:
			self.outStack.pop()
			return
		for i in range(0, len(self.inStack)):
			self.outStack.append(self.inStack.pop())
		self.outStack.pop()

	def peak(self):
		if len(self.outStack) != 0:
			return self.outStack[-1]
		if len(self.inStack) != 0:
			return self.inStack[0]
lines = [line.split() for line in sys.stdin]
queue = Queue()
for i in range(1, len(lines)):
	command = lines[i]
	if len(command) == 1:
		if command[0] == '2':
			queue.dequeue()
		elif command[0] == '3':
			print(queue.peak())
	else:
		value = command[1]
		queue.enqueue(value)


num_queries = int(input())

class MyQueue:

	def __init__(self):
		self.s1 = []

	def enqueue(self, element):
		self.s1.append(element)

	def dequeue(self):
		self.s1 = self.s1[1:]

	def peek(self):
		return self.s1[0]
queue = MyQueue()
for i in range(num_queries):
	query = input()
	operation = query[0]
	if operation == '1':
		queue.enqueue(query[2:])
	if operation == '2':
		queue.dequeue()
	if operation == '3':
		print(queue.peek())


n = int(input())
Queue = []
for _ in range(n):
	s = input()
	k = int(s[0])
	if k == 1:
		Queue.append(int(s[2:]))
	if k == 2:
		Queue.pop(0)
	if k == 3:
		print(Queue[0])


from collections import deque
query_count = int(input())
(primary, aux) = (deque(), deque())
for _ in range(query_count):
	query = input()
	query_type = int(query.split()[0])
	if query_type == 1:
		arg = int(query.split()[1])
		primary.append(arg)
	if query_type == 2:
		if not aux:
			while primary:
				aux.append(primary.pop())
		aux.pop()
	if query_type == 3:
		if not aux:
			while primary:
				aux.append(primary.pop())
		print(aux[-1])


class MyQueue(object):

	def __init__(self):
		self.left = []
		self.right = []

	def peek(self):
		if len(self.left) == 0:
			self.right.reverse()
			self.left = self.right
			self.right = []
		return self.left[-1]

	def pop(self):
		val_to_return = self.peek()
		del self.left[-1]
		return val_to_return

	def put(self, value):
		self.right.append(value)
queue = MyQueue()
t = int(input())
for line in range(t):
	values = map(int, input().split())
	values = list(values)
	if values[0] == 1:
		queue.put(values[1])
	elif values[0] == 2:
		queue.pop()
	else:
		print(queue.peek())


class Queue:

	def __init__(self):
		self.s1 = []
		self.s2 = []

	def peek(self):
		if len(self.s2) < 1:
			for i in range(len(self.s1) - 1, -1, -1):
				self.s2.append(self.s1[i])
			self.s1 = []
		print(self.s2[len(self.s2) - 1])

	def pop(self):
		if len(self.s2) < 1:
			for i in range(len(self.s1) - 1, -1, -1):
				self.s2.append(self.s1[i])
			self.s1 = []
		elem = self.s2[len(self.s2) - 1]
		self.s2.pop()
		return elem

	def push(self, x):
		self.s1.append(x)
q = int(input().strip())
Q = Queue()
for i in range(q):
	inp = input().strip().split(' ')
	if inp[0] == '1':
		Q.push(inp[1])
	elif inp[0] == '2':
		Q.pop()
	elif inp[0] == '3':
		Q.peek()


import sys
s1 = []
s2 = []

def enqueue(val):
	s1.append(val)

def dequeue():
	if not s2:
		while s1:
			s2.append(s1.pop())
	return s2.pop()

def peek():
	print(s2[-1] if s2 else s1[0])
q = int(input().strip())
for i in range(q):
	input_arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	t = input_arr[0]
	if t == 1:
		x = input_arr[1]
		enqueue(x)
	elif t == 2:
		dequeue()
	elif t == 3:
		peek()


op = int(input())
it = 0
queue = list()
for zz in range(op):
	line = input()
	if line[0] == '1':
		(_, el) = map(int, line.split())
		queue.append(el)
	elif line[0] == '2':
		it += 1
	else:
		print(queue[it])


class Queue:

	def __init__(self):
		self.items = []

	def enqueue(self, item):
		self.items.append(item)

	def dequeue(self):
		del self.items[0]

	def print_item(self):
		print(self.items[0])
n = int(input())
q = Queue()
for _ in range(n):
	params = input().split()
	if params[0] == '1':
		q.enqueue(params[1])
	elif params[0] == '2':
		q.dequeue()
	elif params[0] == '3':
		q.print_item()


ENQUEUE = 1
DEQUEUE = 2
PRINT = 3

def read_command():
	parts = input().strip().split(' ')
	cmd = int(parts[0])
	if len(parts) == 1:
		return (cmd, None)
	try:
		arg = int(parts[1])
	except ValueError:
		arg = parts[1]
	return (cmd, arg)

class Stack:

	def __init__(self):
		self._l = []

	def push(self, data):
		self._l.append(data)

	def pop(self):
		return self._l.pop()

	def __len__(self):
		return len(self._l)

	def top(self):
		if self._l:
			return self._l[-1]
		return None

class Queue:

	def __init__(self):
		self._head = Stack()
		self._tail = Stack()

	def enqueue(self, data):
		self._tail.push(data)

	def dequeue(self):
		if self._head:
			return self._head.pop()
		while self._tail:
			self._head.push(self._tail.pop())
		return self._head.pop()

	def print_first(self):
		if self._head:
			print(self._head.top())
			return
		while self._tail:
			self._head.push(self._tail.pop())
		print(self._head.top())

def main():
	q = Queue()
	n_commands = int(input().strip())
	for _ in range(n_commands):
		(command, arg) = read_command()
		if command == ENQUEUE:
			q.enqueue(arg)
		elif command == DEQUEUE:
			q.dequeue()
		elif command == PRINT:
			q.print_first()
main()


class Stack:

	def __init__(self):
		self.stack1 = []
		self.stack2 = []
		self.first = 0

	def enqueue(self, val):
		if len(self.stack1) == 0:
			self.first = val
		self.stack1.append(val)

	def dequeue(self):
		if len(self.stack2) == 0:
			self.move(self.stack1, self.stack2)
		self.stack2.pop()

	def peek(self):
		if len(self.stack2) != 0:
			return self.stack2[-1]
		else:
			return self.first

	def move(self, orig, dest):
		while len(orig) > 0:
			dest.append(orig.pop())
s = Stack()
n = int(input().strip())
for i in range(n):
	(command, *val) = input().strip().split(' ')
	if command == '1':
		s.enqueue(int(val[0]))
	elif command == '2':
		s.dequeue()
	else:
		print(s.peek())


from collections import deque
a = deque()
for _ in range(int(input())):
	e = input().split()
	if e[0] == '1':
		a.append(e[1])
	elif e[0] == '2':
		a.popleft()
	else:
		print(a[0])


(s1, s2) = ([], [])
for i in range(int(input())):
	inp = list(map(int, input().split()))
	if inp[0] == 1:
		s1.append(inp[1])
	elif inp[0] == 2:
		if not s2:
			while s1:
				s2.append(s1.pop(0))
		s2.pop(0)
	elif inp[0] == 3:
		if not s2:
			while s1:
				s2.append(s1.pop(0))
		print(s2[0])


ENQUEUE = 1
DEQUEUE = 2
PRINT = 3

def read_command():
	parts = input().strip().split(' ')
	cmd = int(parts[0])
	if len(parts) == 1:
		return (cmd, None)
	try:
		arg = int(parts[1])
	except ValueError:
		arg = parts[1]
	return (cmd, arg)

class Stack:

	def __init__(self):
		self._l = []

	def push(self, data):
		self._l.append(data)

	def pop(self):
		return self._l.pop()

	def __len__(self):
		return len(self._l)

	def top(self):
		if self._l:
			return self._l[-1]
		return None

class Queue:

	def __init__(self):
		self._head = Stack()
		self._tail = Stack()

	def enqueue(self, data):
		self._tail.push(data)

	def dequeue(self):
		if self._head:
			return self._head.pop()
		return self._tail_to_head().pop()

	def peek(self):
		if self._head:
			return self._head.top()
		return self._tail_to_head().top()

	def _tail_to_head(self):
		while self._tail:
			self._head.push(self._tail.pop())
		return self._head

def main():
	q = Queue()
	n_commands = int(input().strip())
	for _ in range(n_commands):
		(command, arg) = read_command()
		if command == ENQUEUE:
			q.enqueue(arg)
		elif command == DEQUEUE:
			q.dequeue()
		elif command == PRINT:
			print(q.peek())
main()


class Node:

	def __init__(self, value, next=None):
		self.value = value
		self.next = next

class Stack:

	def __init__(self):
		self.head = None

	def push(self, x):
		new_node = Node(x, next=self.head)
		self.head = new_node

	def pop(self):
		to_return = self.head.value
		self.head = self.head.next
		return to_return

	@property
	def empty(self):
		return not self.head

class TwoStackQueue:

	def __init__(self):
		self.inbox = Stack()
		self.outbox = Stack()

	def enqueue(self, x):
		self.inbox.push(x)

	def refill_outbox(self):
		while not self.inbox.empty:
			self.outbox.push(self.inbox.pop())

	def peek(self):
		to_return = self.dequeue()
		self.outbox.push(to_return)
		return to_return

	def dequeue(self):
		if self.outbox.empty:
			self.refill_outbox()
		return self.outbox.pop()
query_count = int(input())
queue = TwoStackQueue()
for _ in range(query_count):
	line = input()
	ints = [int(i) for i in line.split(' ')]
	query_type = ints[0]
	if query_type == 1:
		queue.enqueue(ints[1])
	elif query_type == 2:
		queue.dequeue()
	else:
		print(queue.peek())


(old, new) = ([], [])
for _ in range(int(input())):
	val = list(map(int, input().split()))
	if val[0] == 1:
		new.append(val[1])
	elif val[0] == 2:
		if not old:
			while new:
				old.append(new.pop())
		old.pop()
	else:
		print(old[-1] if old else new[0])


q = int(input().strip())
cmds = [input().strip().split() for _ in range(q)]
from collections import deque
s1 = deque()
s2 = deque()
for c in cmds:
	if c[0] == '1':
		val = c[1]
		s1.append(val)
	else:
		if len(s2) == 0:
			for _ in range(len(s1)):
				s2.append(s1.pop())
		if c[0] == '2':
			s2.pop()
		else:
			print(s2[-1])


n = int(input())
a = []
for x in range(n):
	q = [int(i) for i in input().split(' ')]
	if q[0] == 1:
		a.append(q[1])
	if q[0] == 2:
		a.pop(0)
	if q[0] == 3:
		print(a[0])


import sys
data = sys.stdin.readlines()
n_query = int(data[0].strip())
queries = [list(map(int, line.strip().split(' '))) for line in data[1:]]
queue = []
for query in queries:
	instruct = query[0]
	if instruct == 1:
		num = query[1]
		queue.append(num)
	elif instruct == 2:
		queue.pop(0)
	elif instruct == 3:
		print(queue[0])


class Stack(object):

	def __init__(self):
		self.inbox = []
		self.outbox = []

	def queue(self, data):
		self.inbox.append(data)

	def dequeue(self):
		if self.outbox == []:
			while self.inbox != []:
				self.outbox.append(self.inbox.pop())
		self.outbox.pop()

	def print_last(self):
		if self.outbox == []:
			while self.inbox != []:
				self.outbox.append(self.inbox.pop())
		print(self.outbox[-1])
Q = int(input())
Stack = Stack()
for _ in range(Q):
	L = list(map(int, input().strip().split(' ')))
	if L[0] == 1:
		Stack.queue(L[1])
	elif L[0] == 2:
		Stack.dequeue()
	else:
		Stack.print_last()


n = int(input().strip())
new = []
old = []
for _ in range(n):
	s = [int(x) for x in input().strip().split()]
	if s[0] == 1:
		new.insert(0, s[1])
	elif s[0] == 2:
		new.pop()
	elif s[0] == 3:
		print(new[len(new) - 1])


class Queue:

	def __init__(self):
		self.stack1 = []
		self.stack2 = []

	def enqueue(self, item):
		self.stack1.append(item)

	def dequeue(self):
		if not self.stack2:
			while self.stack1:
				self.stack2.append(self.stack1.pop())
		self.stack2.pop()

	def top(self):
		if not self.stack2:
			while self.stack1:
				self.stack2.append(self.stack1.pop())
		return self.stack2[-1]
queue = Queue()
q = int(input())
for _ in range(q):
	instr = input().split()
	if len(instr) == 2:
		queue.enqueue(int(instr[1]))
	elif int(instr[0]) == 2:
		queue.dequeue()
	else:
		print(queue.top())


size = int(input().strip())
lines = [input().strip() for i in range(0, size)]
stack_new = []
stack_old = []

def move_a_to_b(a, b):
	while a:
		b.append(a.pop())

def enque(item, old, new):
	new.append(item)

def deque(old, new):
	if len(old) < 1:
		move_a_to_b(new, old)
	return old.pop()

def peek_front(old, new):
	if len(old) < 1:
		move_a_to_b(new, old)
	print(old[len(old) - 1])
for line in lines:
	args = line.split()
	operation = int(args[0])
	if operation == 1:
		if len(args) < 2:
			raise ValueError('no argument for enque operation')
		val_to_queue = args[1]
		enque(val_to_queue, stack_old, stack_new)
	elif operation == 2:
		val_dequeued = deque(stack_old, stack_new)
	elif operation == 3:
		peek_front(stack_old, stack_new)
	else:
		raise ValueError('invalid operation')


class Queue:

	def __init__(self):
		self._s1 = []
		self._s2 = []

	def checkS2(self):
		if len(self._s2) == 0:
			while len(self._s1) > 0:
				self._s2.append(self._s1.pop())

	def first(self):
		self.checkS2()
		return self._s2[-1]

	def dequeue(self):
		self.checkS2()
		return self._s2.pop()

	def enqueue(self, v):
		self._s1.append(v)
n = int(input())
q = Queue()
for _ in range(n):
	param = input().split()
	if param[0] == '1':
		q.enqueue(param[1])
	elif param[0] == '2':
		q.dequeue()
	else:
		print(q.first())


import sys

class Queue:

	def __init__(self):
		self.q = list()

	def enqueue(self, x):
		self.q.append(x)

	def dequeue(self):
		tmp = self.q[0]
		self.q = self.q[1:]
		return tmp

	def print_front(self):
		print(self.q[0])
q = Queue()
t = int(input().strip())
for a0 in range(t):
	s = input().strip()
	s = s.split(' ')
	if s[0] == '1':
		q.enqueue(s[1])
	if s[0] == '2':
		q.dequeue()
	if s[0] == '3':
		q.print_front()


q = int(input())
L = []
for _ in range(q):
	a = [int(x) for x in input().split()]
	if a[0] == 1:
		L.append(a[1])
	elif a[0] == 2:
		L.pop(0)
	elif a[0] == 3:
		print(L[0])


numLines = int(input())

def readInputLine():
	return [int(x) for x in input().split(' ')]

def swapData(stackWithData, emptyStack):
	for i in range(len(stackWithData)):
		emptyStack.append(stackWithData.pop())
enqueueStack = []
dequeueStack = []
for i in range(numLines):
	inputArray = readInputLine()
	if inputArray[0] == 1:
		enqueueStack.append(inputArray[1])
	elif inputArray[0] == 2:
		if len(dequeueStack) == 0:
			swapData(enqueueStack, dequeueStack)
		dequeueStack.pop()
	else:
		if len(dequeueStack) == 0:
			swapData(enqueueStack, dequeueStack)
		print(dequeueStack[-1])


class Queue(object):

	def __init__(self):
		self.main = []
		self.second = []

	def _reorderStacks(self):
		if not self.main:
			while self.second:
				self.main.append(self.second.pop())

	def enqueue(self, element):
		self.second.append(element)

	def dequeue(self):
		self._reorderStacks()
		self.main.pop()

	def peek(self):
		self._reorderStacks()
		return self.main[-1]
q = Queue()
for _ in range(int(input())):
	op = input().split(' ')
	if op[0] == '1':
		q.enqueue(op[1])
	elif op[0] == '2':
		q.dequeue()
	else:
		print(q.peek())