KIẾN THỨC

BÀI TẬP

Cho n truy vấn thao tác với một hàng đợi hai đầu (deque). Ban đầu deque rỗng. Có 4 loại thao tác:

Loại 1 x: Thêm số nguyên x vào cuối deque.

Loại 2 x: Thêm số nguyên x vào đầu deque.

Loại 3: Xóa phần tử ở đầu deque và in ra giá trị đó. Nếu deque rỗng, in ra -1.

Loại 4: Xóa phần tử ở cuối deque và in ra giá trị đó. Nếu deque rỗng, in ra -1.

Dữ liệu vào (Đọc từ file DEQUE1.INP):

Dòng đầu tiên là số nguyên n (1 <= n <= 10⁵) là số lượng truy vấn.

n dòng tiếp theo, mỗi dòng chứa thông tin của một truy vấn (gồm 1 hoặc 2 số nguyên tùy loại thao tác).

Dữ liệu ra (Ghi ra file DEQUE1.OUT):

Mỗi khi gặp thao tác loại 3 hoặc 4, in ra kết quả trên một dòng.

Ví dụ

Input:

7
1 10
2 20
1 30
3
4
3
3

Output:

20
30
10
-1

Giải thích:

1 10: Thêm 10 vào cuối. Hàng đợi: [10]

2 20: Thêm 20 vào đầu. Hàng đợi: [20, 10]

1 30: Thêm 30 vào cuối. Hàng đợi: [20, 10, 30]

3: Lấy ở đầu ra. In 20. Hàng đợi còn: [10, 30]

4: Lấy ở cuối ra. In 30. Hàng đợi còn: [10]

3: Lấy ở đầu ra. In 10. Hàng đợi rỗng: []

3: Lấy ở đầu ra. Hàng đợi rỗng, in -1.