Giá trị xuất hiện nhiều nhất

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

• 1 x: Thêm phần tử có giá trị \(x\) vào tập hợp.

• 2 x: Xóa một phần tử có giá trị \(x\) khỏi tập hợp (nếu trong tập hợp có nhiều phần tử giá trị \(x\) thì chỉ xóa đúng một phần tử; nếu không có phần tử \(x\) nào thì bỏ qua truy vấn này).

• 3 a b: Tìm số xuất hiện nhiều nhất trong các số thuộc đoạn \([a, b]\) trong tập hợp. Nếu có nhiều số cùng xuất hiện nhiều nhất thì in ra số có giá trị nhỏ nhất. Nếu trong tập hợp không có phần tử nào thuộc đoạn \([a, b]\) thì in ra \(-1\).

Input

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

• \(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong ba định dạng đã nêu ở trên (\(1 \le x, a, b \le 10^9\)).

Output

Với mỗi truy vấn loại \(3\), in ra trên một dòng một số nguyên là đáp án.

Example

Input:

8
1 1 3
1 2 2
3
1 2 1
3
1 5 10
2 5 7
3

Output:

1
2
5