Tập hợp

Cho một tập hợp \(S\) ban đầu rỗng. Bạn cần xử lí \(q\) truy vấn thuộc một trong 4 dạng sau:

• 1 x: Thêm số nguyên \(x\) vào tập hợp \(S\).

• 2 x: Xóa số nguyên \(x\) khỏi tập hợp \(S\) (nếu có nhiều phần tử giá trị \(x\) thì chỉ xóa 1 phần tử, nếu không có phần tử nào thì bỏ qua).

• 3: In ra giá trị nhỏ nhất trong tập hợp \(S\).

• 4: In ra giá trị lớn nhất trong tập hợp \(S\).

Dữ liệu vào đảm bảo khi thực hiện truy vấn 3 và 4 thì tập hợp \(S\) không rỗng.

Input

• Dòng đầu tiên gồm số nguyên \(q\) (\(1 \le q \le 10^5\)).

• \(q\) dòng tiếp theo, mỗi dòng gồm một truy vấn thuộc một trong các dạng đã mô tả ở trên (\(1 \le x \le 10^9\)).

Output

Với mỗi truy vấn loại \(3\) hoặc \(4\), in ra trên một dòng một số nguyên là đáp án nếu tồn tại, ngược lại in ra \(-1\).

Example

Input:

8
4 5
1 2
1 3
1 2
3 2
1 5
2 3
4 4

Output:

-1
3
2

Note

Sau các truy vấn \(1\ 2\), \(1\ 3\), \(1\ 2\), tập hợp \(S\) gồm các phần tử \(\{2, 2, 3\}\).

• Truy vấn \(4\ 5\): tập hợp đang rỗng nên không có giá trị nào không vượt quá \(5\), in ra \(-1\).

• Truy vấn \(3\ 2\): giá trị nhỏ nhất lớn hơn \(2\) trong \(\{2, 2, 3\}\) là \(3\).

• Sau truy vấn \(1\ 5\), tập hợp là \(\{2, 2, 3, 5\}\). Sau truy vấn \(2\ 3\) (xóa một phần tử \(3\)), tập hợp là \(\{2, 2, 5\}\).

• Truy vấn \(4\ 4\): giá trị lớn nhất không vượt quá \(4\) trong \(\{2, 2, 5\}\) là \(2\).