Bộ lệnh BST động (Dynamic BST Commands)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Ban đầu có một BST rỗng. Hãy xử lý lần lượt $q$ lệnh; trạng thái cây sau một lệnh là trạng thái đầu vào của lệnh tiếp theo.

Có bốn loại lệnh:

I x: chèn khóa $x$ vào BST. Nếu $x$ đã tồn tại, cây không thay đổi.

D x: xóa khóa $x$ khỏi BST. Nếu $x$ không tồn tại, cây không thay đổi. Nếu nút cần xóa có hai con, dùng inorder successor, tức nút nhỏ nhất trong cây con phải, để thay thế.

F x: kiểm tra khóa $x$ có đang tồn tại trong cây hay không.

P: in toàn bộ khóa hiện có theo thứ tự inorder.

Input

Dòng đầu chứa số nguyên $q$ — số lệnh.

$q$ dòng tiếp theo, mỗi dòng chứa đúng một lệnh theo một trong bốn dạng I x, D x, F x hoặc P.

Output

Với mỗi lệnh F x, in một dòng YES nếu $x$ đang tồn tại, ngược lại in NO.

Với mỗi lệnh P, in các khóa hiện có theo thứ tự tăng dần, cách nhau bởi một dấu cách; nếu cây rỗng, in EMPTY.

Các lệnh I và D không tạo output.

Subtask

Subtask 1 (20 điểm): $1\le q\le 20$.

Subtask 2 (30 điểm): $1\le q\le 5000$.

Subtask 3 (50 điểm): $1\le q\le 200000$.

Trong tất cả các subtask, mọi khóa $x$ trong các lệnh là số nguyên có dấu 64-bit.

Ví dụ

Input

8
I 8
I 3
I 10
F 3
D 8
F 8
P
P

Output

YES
NO
3 10
3 10

Giải thích

Sau ba lệnh đầu, cây chứa các khóa $3,8,10$. Vì $3$ đang tồn tại nên lệnh F 3 in YES.

Lệnh D 8 xóa khóa $8$. Sau đó cây chỉ còn $3$ và $10$, nên F 8 in NO. Hai lệnh P liên tiếp không làm thay đổi cây và đều in dãy inorder 3 10.