use std::alloc::{alloc, dealloc, Layout};
use std::io::{self, BufRead};
use std::ptr;

struct Node {
    val: i32,
    left: *mut Node,
    right: *mut Node,
}

impl Node {
    unsafe fn new(val: i32) -> *mut Node {
        let layout = Layout::new::<Node>();
        let ptr = alloc(layout) as *mut Node;
        if !ptr.is_null() {
            ptr::write(ptr, Node { val, left: ptr::null_mut(), right: ptr::null_mut() });
        }
        ptr
    }
}

unsafe fn insert(root: *mut Node, val: i32) -> *mut Node {
    if root.is_null() {
        return Node::new(val);
    }
    if val < (*root).val {
        (*root).left = insert((*root).left, val);
    } else if val > (*root).val {
        (*root).right = insert((*root).right, val);
    }
    root
}

unsafe fn find_min(root: *mut Node) -> i32 {
    let mut curr = root;
    while !(*curr).left.is_null() {
        curr = (*curr).left;
    }
    (*curr).val
}

unsafe fn delete(root: *mut Node, val: i32) -> *mut Node {
    if root.is_null() { return ptr::null_mut(); }

    if val < (*root).val {
        (*root).left = delete((*root).left, val);
    } else if val > (*root).val {
        (*root).right = delete((*root).right, val);
    } else {
        if (*root).left.is_null() {
            let temp = (*root).right;
            dealloc(root as *mut u8, Layout::new::<Node>());
            return temp;
        } else if (*root).right.is_null() {
            let temp = (*root).left;
            dealloc(root as *mut u8, Layout::new::<Node>());
            return temp;
        } else {
            let min_val = find_min((*root).right);
            (*root).val = min_val;
            (*root).right = delete((*root).right, min_val);
        }
    }
    root
}

unsafe fn inorder(root: *mut Node, out: &mut String) {
    if root.is_null() { return; }
    inorder((*root).left, out);
    out.push_str(&(*root).val.to_string());
    out.push(' ');
    inorder((*root).right, out);
}

unsafe fn preorder(root: *mut Node, out: &mut String) {
    if root.is_null() { return; }
    out.push_str(&(*root).val.to_string());
    out.push(' ');
    preorder((*root).left, out);
    preorder((*root).right, out);
}

fn main() {
    let stdin = io::stdin();
    let mut reader = stdin.lock();
    let mut line = String::new();

    if reader.read_line(&mut line).is_err() { return; }
    let n: i32 = line.trim().parse().unwrap_or(0);

    let mut root: *mut Node = ptr::null_mut();

    unsafe {
        for _ in 0..n {
            line.clear();
            if reader.read_line(&mut line).unwrap_or(0) == 0 { break; }
            let mut parts = line.split_whitespace();
            let cmd = parts.next().unwrap_or("");
            let val_str = parts.next().unwrap_or("");
            if let Ok(val) = val_str.parse::<i32>() {
                if cmd == "Insert" {
                    root = insert(root, val);
                } else if cmd == "Remove" {
                    root = delete(root, val);
                }
            }
        }

        if !root.is_null() {
            let mut out = String::with_capacity(1024 * 1024);
            inorder(root, &mut out);
            println!("{}", out.trim_end());
            
            println!();
            
            out.clear();
            preorder(root, &mut out);
            println!("{}", out.trim_end());
        }
    }
}