Cho mảng ~a~ gồm ~n~ phần tử, thực hiện ~q~ truy vấn gồm một trong các loại sau:

• ~1~ ~x~: Tăng tất cả phần tử trong mảng lên ~x~ đơn vị.
• ~2~ ~x~: Giảm tất cả phần tử trong mảng đi ~x~ đơn vị.
• ~3~ ~x~: Thêm phần tử ~x~ vào đầu dãy. Sau thao tác này, ~n~ tăng lên ~1~.
• ~4~ ~x~: Thêm phần tử ~x~ vào cuối dãy. Sau thao tác này, ~n~ tăng lên ~1~.
• ~5~: Sắp xếp dãy theo thứ tự tăng dần.
• ~6~: Sắp xếp dãy theo thứ tự giảm dần.
• ~7~: In ra phần tử đầu tiên của dãy, sau đó bỏ phần tử đó đi. Dữ liệu đảm bảo dãy có ít nhất ~1~ phần tử.
• ~8~: In ra phần tử cuối cùng của dãy, sau đó bỏ phần tử đó đi. Dữ liệu đảm bảo dãy có ít nhất ~1~ phần tử.

Yêu cầu: Với mỗi truy vấn loại ~7~ và ~8~, in ra kết quả tương ứng.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 2 \times 10^5~) - số phần tử trong mảng và số truy vấn.

Dòng thứ hai gồm ~n~ số nguyên ~a_i~ (~0 \le |a_i| \le 10^9~) thể hiện mảng.

~q~ dòng tiếp theo, mỗi dòng thể hiện một truy vấn. Tất cả ~x~ trong mọi truy vấn sẽ có giá trị tuyệt đối không quá ~10^9~.

Output

Với mỗi truy vấn loại ~7~ hoặc ~8~, in ra đáp án trên một dòng.

Sample Input

5 4
4 5 6 7 8
8
6
3 3
7

Sample Output

8
3

Mảng ban đầu là ~4, 5, 6, 7, 8~.

Sau truy vấn ~1~, mảng là ~4, 5, 6, 7~.

Sau truy vấn ~2~, mảng là ~7, 6, 5, 4~.

Sau truy vấn ~3~, mảng là ~3, 7, 6, 5, 4~.

Sau truy vấn ~4~, mảng là ~7, 6, 5, 4~.