use std::io::{self, BufRead};

struct BST {
    val: i32,
    left: Option<Box<BST>>,
    right: Option<Box<BST>>,
}

impl BST {
    fn new(val: i32) -> Self {
        BST {
            val,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, val: i32) {
        if val < self.val {
            match self.left.as_mut() {
                Some(left) => left.insert(val),
                None => self.left = Some(Box::new(BST::new(val))),
            }
        } else if val > self.val {
            match self.right.as_mut() {
                Some(right) => right.insert(val),
                None => self.right = Some(Box::new(BST::new(val))),
            }
        }
    }

    fn find_min(&self) -> i32 {
        match self.left.as_ref() {
            Some(left) => left.find_min(),
            None => self.val,
        }
    }

    fn delete(node: Option<Box<BST>>, val: i32) -> Option<Box<BST>> {
        let mut node = node?;

        if val < node.val {
            node.left = Self::delete(node.left.take(), val);
        } else if val > node.val {
            node.right = Self::delete(node.right.take(), val);
        } else {
            if node.left.is_none() {
                return node.right;
            } else if node.right.is_none() {
                return node.left;
            } else {
                let min_right = node.right.as_ref().unwrap().find_min();
                node.val = min_right;
                node.right = Self::delete(node.right.take(), min_right);
            }
        }
        Some(node)
    }

    fn inorder(&self, res: &mut Vec<String>) {
        if let Some(left) = self.left.as_ref() { 
            left.inorder(res); 
        }
        res.push(self.val.to_string());
        if let Some(right) = self.right.as_ref() { 
            right.inorder(res); 
        }
    }

    fn preorder(&self, res: &mut Vec<String>) {
        res.push(self.val.to_string());
        if let Some(left) = self.left.as_ref() { 
            left.preorder(res); 
        }
        if let Some(right) = self.right.as_ref() { 
            right.preorder(res); 
        }
    }
}

fn main() {
    let stdin = io::stdin();
    let mut reader = stdin.lock();
    let mut line = String::new();
    
    reader.read_line(&mut line).unwrap();
    let n: i32 = line.trim().parse().unwrap_or(0);
    
    let mut bst: Option<Box<BST>> = None;

    for _ in 0..n {
        line.clear();
        reader.read_line(&mut line).unwrap();
        let parts: Vec<&str> = line.split_whitespace().collect();
        if parts.len() < 2 { continue; }
        
        let val = parts[1].parse::<i32>().unwrap();
        if parts[0] == "Insert" {
            if let Some(tree) = bst.as_mut() {
                tree.insert(val);
            } else {
                bst = Some(Box::new(BST::new(val)));
            }
        } else {
            bst = BST::delete(bst, val);
        }
    }

    if let Some(tree) = bst {
        let mut in_res = Vec::new();
        tree.inorder(&mut in_res);
        println!("{} ", in_res.join(" "));
        
        println!();

        let mut pre_res = Vec::new();
        tree.preorder(&mut pre_res);
        println!("{} ", pre_res.join(" "));
    }
}