Hàng đợi hai đầu (Double-ended Queue - Deque) là một cấu trúc dữ liệu cực kỳ linh hoạt cho phép bạn thêm hoặc xóa các phần tử ở cả đầu (front) và cuối (back) của hàng với độ phức tạp thời gian tối ưu \(O(1)\).

Để làm quen với cấu trúc dữ liệu này, bạn hãy lập trình mô phỏng một cấu trúc Deque hỗ trợ các truy vấn sau:

• 1 x: Thêm số nguyên \(x\) vào đầu (front) của Deque.
• 2 x: Thêm số nguyên \(x\) vào cuối (back) của Deque.
• 3: Xóa phần tử ở đầu (front) của Deque (nếu Deque rỗng, bỏ qua).
• 4: Xóa phần tử ở cuối (back) của Deque (nếu Deque rỗng, bỏ qua).
• 5: In ra phần tử ở đầu (front) của Deque. Nếu Deque rỗng, in ra -1.
• 6: In ra phần tử ở cuối (back) của Deque. Nếu Deque rỗng, in ra -1.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(Q\) (\(1 \le Q \le 10^5\)) — số lượng truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng trên.

Định dạng đầu ra

• Với mỗi truy vấn loại 5 và 6, in ra kết quả tương ứng trên một dòng riêng biệt.

Ví dụ

Input:

8
2 5
1 3
5
6
3
5
4
5

Output:

3
5
5
-1

Ràng buộc

• 30% số điểm ứng với \(Q \le 1000\).
• 70% số điểm còn lại không có ràng buộc gì thêm.
• Các giá trị thêm vào thỏa mãn \(1 \le x \le 10^9\).