use std::{
    fs::File,
    error::Error,
    io::{BufReader, BufRead, LineWriter, Write},    
    cell::RefCell,
};

#[derive(Debug, Clone)]
struct Trie {
    cnt: i32,
    fii: RefCell<Vec<Trie>>,
    flag: [bool; 26],
    nrfii: i32,
}

impl Default for Trie {
    fn default() -> Trie {
        Trie {
            cnt: 0,
            fii: RefCell::<Vec::<Trie>>::new(Vec::<Trie>::new()),
            flag: [false; 26],
            nrfii: 0,
        }
    }
}

impl Trie {
    fn add(&mut self, word: &str) {
        if word.len() == 0 {
            self.cnt += 1;
            return;
        }
        if self.fii.borrow().len() == 0 {
            self.fii.borrow_mut().resize(26, Trie::default());
        }
        let c = (word.as_bytes()[0] - 97) as usize;                
        if self.flag[c] == false {
            self.flag[c] = true;
            self.nrfii += 1;
        }
        let next = &mut self.fii.borrow_mut()[c];
        next.add(&word[1..]);
    }
    fn del(&mut self, word: &str) {
        if word.len() == 0 {
            self.cnt -= 1;
            return;
        }
        let c = (word.as_bytes()[0] - 97) as usize;        
        let next = &mut self.fii.borrow_mut()[c];        
        next.del(&word[1..]);
        if next.cnt == 0 && next.nrfii == 0 {
            self.flag[c] = false;
            self.nrfii -= 1;
            next.fii.replace(Vec::<Trie>::new());                
        }
    }
    fn count(&mut self, word: &str) -> i32 {
        if word.len() == 0 {
            return self.cnt;
        }
        let c = (word.as_bytes()[0] - 97) as usize;
        if self.flag[c] == false {
            return 0;
        }
        let next = &mut self.fii.borrow_mut()[c];
        return next.count(&word[1..]);
    }
    fn longest_prefix(&mut self, word: &str) -> i32 {
        if word.len() == 0 {
            return 0;
        }
        let c = (word.as_bytes()[0] - 97) as usize;        
        if self.flag[c] == true {
            let next = &mut self.fii.borrow_mut()[c];
            return 1 + next.longest_prefix(&word[1..]);
        }
        0
    }
}

fn main() -> Result<(), Box<dyn Error>> {
    let file = File::open("trie.in")?;
    let out_file = File::create("trie.out")?;
    let mut writer = LineWriter::new(out_file);
    let reader = BufReader::new(file);    
    let mut trie = Trie::default();
    // println!("{:?}", t);
    for line in reader.lines() {
        // writeln!(writer, "{}", line?)?;
        let line_s = line?;  
        if line_s.len() == 0 {
            continue;
        }      
        let mut it = line_s.split_whitespace();
        let op: i32 = it.next().unwrap().parse()?;
        let word = it.next().unwrap();
        if op == 0 {
            trie.add(word);
        } else if op == 1 {
            trie.del(word);
        } else if op == 2 {
            writeln!(writer, "{}", trie.count(word))?;
        } else {
            writeln!(writer, "{}", trie.longest_prefix(word))?;
        }
    }
    Ok(())
}