Trung vị

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

• 1 x: Nếu phần tử \(x\) hiện đang không có trong tập hợp, thêm phần tử \(x\) vào tập hợp. Ngược lại (nếu \(x\) đã có trong tập hợp), xóa phần tử \(x\) khỏi tập hợp.

• 2: Tìm trung vị của tập hợp. Sắp xếp các phần tử của \(S\) theo thứ tự từ bé đến lớn, đánh số thứ tự các phần tử từ \(1\). Gọi \(n\) là số phần tử hiện có của \(S\) (khi gặp truy vấn này, \(S\) luôn có ít nhất một phần tử):

  • Nếu \(n\) lẻ, trung vị là phần tử có chỉ số \(\frac{n + 1}{2}\).

• Nếu \(n\) chẵn, trung vị là trung bình cộng của phần tử có chỉ số \(\frac{n}{2}\) và phần tử có chỉ số \(\frac{n}{2} + 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 mô tả một truy vấn theo đúng định dạng đã nêu ở trên (\(1 \le x \le 10^9\)).

Output

Với mỗi truy vấn loại \(2\), in ra trên một dòng giá trị trung vị tương ứng. Nếu đáp án là số nguyên, in ra số nguyên đó (không có phần thập phân). Nếu đáp án là số thực không nguyên, làm tròn và in với đúng một chữ số sau dấu phẩy.

Example

Input:

8
1 5
2
1 6
2
1 5
1 8
1 10
2

Output:

5
5.5
8

Note

Diễn giải ví dụ trên:

• Sau truy vấn 1 5: \(S = \{5\}\). Truy vấn 2 cho kết quả trung vị là \(5\).

• Sau truy vấn 1 6: \(S = \{5, 6\}\). Truy vấn 2 cho kết quả trung vị là \(\frac{5 + 6}{2} = 5.5\).

• Truy vấn 1 5 tiếp theo xóa \(5\) khỏi \(S\), được \(S = \{6\}\). Sau đó thêm \(8\) và \(10\), được \(S = \{6, 8, 10\}\). Truy vấn 2 cuối cùng cho kết quả trung vị là \(8\) (phần tử ở giữa).