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 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, rootId) {
    const walked = ['', ''];
    preParse(tree, rootId, walked);
    inParse(tree, rootId, 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[1]){
            insert(tree, rootId, parseInt(order[1], 10));
        } else {
            // console.log(tree);
            printOut(tree, rootId);
        }
    }
}


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

