#include <iostream>
#include <string>
#include <fstream>
#include <chrono>
#include <vector>
#include <iomanip>

using namespace std;

struct Node{
    int val;
    Node* left = nullptr;
    Node* right = nullptr;
};

Node* addNode(Node* root, int x){
    if(root == nullptr) return new Node{x, nullptr, nullptr};

    if(x < root->val)
        root->left = addNode(root->left, x);
    else if(x > root->val)
        root->right = addNode(root->right, x);
    return root;
}

bool existInBST(Node* root, int x){
    if(root == nullptr) return false;
    if(root->val == x) return true;
    if(x < root->val) return existInBST(root->left, x);
    return existInBST(root->right, x);
}

void inorder(Node* root){
    if(root == nullptr) return;

    if(root->left != nullptr) inorder(root->left);
    cout << root->val << " ";
    if(root->right != nullptr) inorder(root->right);
}

void preorder(Node* root){
    if(root == nullptr) return;

    cout << root->val << " ";
    if(root->left != nullptr) preorder(root->left);
    if(root->right != nullptr) preorder(root->right);
}

void postorder(Node* root){
    if(root == nullptr) return;

    if(root->left != nullptr) postorder(root->left);
    if(root->right != nullptr) postorder(root->right);
    cout << root->val << " ";
}

Node* get(Node* cur){
    cur = cur->right;
    while(cur != nullptr && cur->left != nullptr)
        cur = cur->left;
    return cur;
}

Node* deleteNode(Node* root, int data){
    if(root == nullptr) return root;

    if(data < root->val){
        root->left = deleteNode(root->left, data);
    }
    else if(data > root->val){
        root->right = deleteNode(root->right, data);
    }
    else{
        if(root->left == nullptr){
            Node* tmp = root->right;
            delete root;
            return tmp;
        }
        if(root->right == nullptr){
            Node* tmp = root->left;
            delete root;
            return tmp;
        }

        Node* succ = get(root);
        root->val = succ->val;
        root->right = deleteNode(root->right, succ->val);
    }
    return root;
}

int main(){
    int q;
    Node* root = nullptr;
    while(cin >> q){
        if(q == 1){
            int x; cin >> x;
            root = addNode(root, x);
        }
        else if(q == 2){
            string s; cin >> s;
            if(s == "NLR") preorder(root);
            else if(s == "LNR") inorder(root);
            else postorder(root);
            cout << '\n';
        }
        else if(q == 3){
            int x; cin >> x;
            bool found = existInBST(root, x);
            if(found) cout << "YES";
            else cout << "NO";
            cout << '\n';
        }
        else{
            int x; cin >> x;
            root = deleteNode(root, x);
        }
    }
    return 0;
}