function insert(tree, rootId, z) {
    let y = null;
    let x = tree[rootId];
    while (x) {
        y = x;
        if (z < x.key) {
            x = tree[x.left];
        } else {
            x = tree[x.right];
        }
    }

    if (y === null) {
        tree[rootId] = {key: z, parent: y, left: null, right: null};
    } else if (z < y.key) {
        y.left = z;
        tree[z] = {key: z, parent: y ? y.key : null, left: null, right: null};
    } else {
        y.right = z;
        tree[z] = {key: z, parent: y ? y.key : null, left: null, right: null};
    }
}

function find(tree, nodeId, k) {
    let node = tree[nodeId];
    while (node.key !== null && node.key !== k) {
        if (node.key < k) {
            node = node.right ? tree[node.right] : null;
        } else {
            node = node.left ? tree[node.left] : null;
        }
        if (!node) return;
    }
    return node;
}

function del(tree, nodeId) {
    const node = tree[parseInt(nodeId, 10)];
    let y = null;
    let x = null;
    if(node.left === null || node.right === null){
        y = node;
    } else {
        y = getSuccessor(tree, node);
    }

    if(y.left !== null){
        x = tree[y.left];
    } else {
        x = tree[y.right];
    }

    if(x){
        x.parent = y.parent;
    }

    if(y.parent === null){
        x.key = y.key;
        tree[y.key] = x;
    } else if(y.key === tree[y.parent].left){
        tree[y.parent].left = x ? x.key : null;
    } else {
        tree[y.parent].right = x ? x.key: null;
    }

    if(y !== node){
        if(tree[node.parent].left === parseInt(nodeId, 10)){
            tree[node.parent].left = y.key;
        } else {
            tree[node.parent].right = y.key;
        }
        if(tree[node.left]) tree[node.left].parent = y.key;
        if(tree[node.right]) tree[node.right].parent = y.key;
        node.key = y.key;
        tree[y.key] = node;
    }
}

function getSuccessor(tree, node) {
    if(node.right !== null){
        return getMin(tree, node.right);
    }
    let y = node.parent;
    while(y !== null && node.key === tree[y].right){
        node = tree[y];
        y = node.parent;
    }
    return tree[y];
}

function getMin(tree, nodeId) {
    let node = tree[nodeId];
    while(node.left !== null){
        node = tree[node.left];
    }
    return node;
}


function preParse(inputs, idx, walked) {
    if (!idx) {
        return;
    }
    walked[0] += ' ';
    walked[0] += inputs[idx].key;
    preParse(inputs, inputs[idx].left, walked);
    preParse(inputs, inputs[idx].right, walked);
}

function inParse(inputs, idx, walked) {
    if (!idx) {
        return;
    }
    inParse(inputs, inputs[idx].left, walked);
    walked[1] += ' ';
    walked[1] += inputs[idx].key;
    inParse(inputs, inputs[idx].right, walked);
}

function printOut(tree, nodeId) {
    const walked = ['', ''];
    preParse(tree, nodeId, walked);
    inParse(tree, nodeId, walked);

    console.log(walked[1]);
    console.log(walked[0]);
}


function main(_stdin) {
    const stdin = _stdin.split('\n');
    const len = stdin.shift();
    const inputs = stdin.filter((e, i) => i < len);

    const tree = [];
    const rootId = parseInt(inputs[0].split(' ')[1], 10);
    for (const input of inputs) {
        const order = input.split(' ');
        if (order[0] === 'insert') {
            insert(tree, rootId, parseInt(order[1], 10));
        } else if (order[0] === 'find') {
            console.log(find(tree, rootId, parseInt(order[1], 10)) ? 'yes' : 'no');
        } else if (order[0] === 'delete') {
            del(tree, order[1]);
        } else {
            // print
            printOut(tree, rootId);
        }
    }
}


main(require('fs').readFileSync('/dev/stdin', 'utf8'));

