Dynamic BST Commands

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Initially the BST is empty. Process $q$ commands in order; the tree state after one command is the starting state for the next command.

There are four command types:

I x: insert key $x$. If $x$ already exists, do nothing.

D x: delete key $x$. If $x$ does not exist, do nothing. If the deleted node has two children, use its inorder successor, the minimum node in its right subtree, as the replacement.

F x: test whether key $x$ currently exists.

P: print all current keys in inorder.

Input

The first line contains $q$ — the number of commands.

Each of the next $q$ lines contains exactly one command in one of the forms I x, D x, F x, or P.

Output

For every F x, print YES if $x$ exists and NO otherwise.

For every P, print all current keys in increasing order separated by one space, or EMPTY if the tree is empty.

Commands I and D produce no output.

Subtasks

Subtask 1 (20 points): $1\le q\le 20$.

Subtask 2 (30 points): $1\le q\le 5000$.

Subtask 3 (50 points): $1\le q\le 200000$.

In all subtasks, every command key $x$ is a signed 64-bit integer.

Examples

Input

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

Output

YES
NO
3 10
3 10

Explanation

After the first three commands, the tree contains $3,8,10$, so F 3 prints YES.

Command D 8 removes key $8$. The tree then contains only $3$ and $10$, so F 8 prints NO. The two consecutive P commands do not modify the tree and both print 3 10.