#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <fcntl.h>
#include <malloc.h>
 
#define CH (*s - 'a')
 
struct TrieNode {
	struct TrieNode *parent;
	unsigned int childrenMask;
	char childrenCount; // useful for deletion
	char freq; // nr of appearances of the word formed by the characters belonging to the path starting at root and ending here
	short int unsused;
	struct TrieNode *child[29];
};
typedef struct TrieNode TrieNode;

TrieNode real_mem[115001];
TrieNode *mem; // chunk of 115000 nodes
TrieNode *free_index[115000];
TrieNode *T;  // first node in chunk we'll be using as root
char input[2000000], output[200000];
int iindex, oindex, ch, isnull, t, alloc_cnt = 1, first_free_index;
 
 
static inline void add(TrieNode *node, char *s) {  // assume word '\0' terminated
	for (;;) {
		if (s[0] == '\n') { 
			node->freq++;
		    return;
		}
		ch = *s - 'a';
		/*isnull = (node->child[ch] == NULL);
		node->childrenCount += isnull;
		node->child[ch] = (isnull ? free_index[first_free_index--] : node->child[ch]);
		node->child[ch]->parent = (isnull ? node : node->child[ch]->parent);
		node = node->child[ch];
		s++;*/

		isnull = (node->child[ch] == NULL);
		node->childrenCount += isnull;
		(isnull ? (node->child[ch] = free_index[first_free_index--]) : 0);
		(isnull ? (node->child[ch]->parent = node) : 0);
		node = node->child[ch];
		s++;
		
		/*if (node->child[ch] == NULL) {
			node->childrenCount++;
			node->child[ch] = free_index[first_free_index--];
			node->child[ch]->parent = node;
		}
		node = node->child[ch];
		s++;*/
	}
}
static inline void rm(TrieNode *node, char *s) {
	while (1) {
		if (s[0] == '\n') { 
		    node->freq--; /* we're guaranteed to find the element on remove op so no need to test freq here */
		    node = ((node->freq == 0 && node->childrenCount == 0) ? node->parent : NULL);
		    break;
		}
		node = node->child[CH];
		s++;
	}
	s--;
	/* go back up the tree and see which other nodes need to be remove (if any)*/
	while (node != NULL) {
		ch = *s - 'a';
		free_index[++first_free_index] = node->child[ch];
		node->child[ch] = 0;
		node->childrenCount--;
		node = ((node->freq == 0 && node->childrenCount == 0) ? node->parent : NULL);
		s--;
	}
}
static inline int query(TrieNode *node, char *s) {
	while (1) {
		if (s[0] == '\n')
		    return node->freq;
		node = node->child[CH];
	    if (node == NULL)
	        return 0;
	    s++;
	}
	return 0;
}
static inline int prefix(TrieNode *node, char *s) {	 
    t = 0;
	while (1) {
		node = node->child[CH];
		if (!node || s[0] == '\n')
		    return t;
		s++;
		t++;
	}
}
static inline void inorder(TrieNode *node, char *buf, int k) {
	int i;
	
	if (node->freq > 0) {
		buf[k] = '\0';
		printf("%s\n", buf);
	}
	for (i = 0; i < 26; i++)
	    if (node->child[i]) {
	    	buf[k] = i+'a';
	    	inorder(node->child[i], buf, k+1);
		}
}
 
void run() {
	char *s, op;
	int i = 0, nr, j = 0;
	int fd_in, fd_out;

    iindex = oindex = ch = isnull = t = first_free_index = 0;
    alloc_cnt = 1;
 
    fd_in  = open("trie.in",  O_RDONLY);
	fd_out = open("trie.out", O_WRONLY | O_CREAT | O_TRUNC, 0644);
	//fd_in  = open("grader_test20.in",  O_RDONLY);
	//fd_out = open("grader_test20.out", O_WRONLY | O_CREAT | O_TRUNC, 0644);
	//memset(mem, 0, 115000*(sizeof(TrieNode)));
	mem = (((unsigned int)&real_mem + (64 - 1)) & ~(64 - 1));  // memalign to 64 bytes
	T = mem;
	T->freq = 1;
	
	iindex = read(fd_in, input, 2000000);
    /* using index 0 in mem[] for root, put the rest in free_index[]; do this in an attempt to somewhat speculate
	   cache locality ... instead of advancing towards the end of the array with each new node, try to reuse the freed ones */
    for (i = 114999; i>=1; i--)
        free_index[j++] = mem+i;
    first_free_index = j-1; 
 
	while (1) {
		s = input+i+2;
		switch(input[i]) {
			case '0':
				add(T, s);
			    break;
			case '1':
				rm(T, s);
			    break;
			case '2':
				nr = query(T, s);
				oindex += sprintf(output+oindex, "%d\n", nr);
			    break;
			case '3':
				nr = prefix(T, s);
				oindex += sprintf(output+oindex, "%d\n", nr);
			    break;
		}
		i += 3;
		while (1) {
			if (input[i] == '\n')
			    break;
			i++;
		}
		//input[i++] = '\0';
		i++;
		if (i >= iindex)
	        break;
	}
	write(fd_out, output, oindex);
	oindex = 0;
	close(fd_in);
	close(fd_out);
	//inorder(T, buf, 0);
}

int main() {
	struct timespec start, stop;
	int i;
	
	/*for (i = 0; i < 10; i++) {
		clock_gettime( CLOCK_REALTIME, &start);
		run();
		clock_gettime( CLOCK_REALTIME, &stop);
		printf( "%d seconds %f milisec\n", stop.tv_sec - start.tv_sec - (start.tv_nsec > stop.tv_nsec), 
		                                       (stop.tv_nsec - start.tv_nsec + (start.tv_nsec > stop.tv_nsec)*1000000000)/1000000.0);
	}*/
	run();
	
	return 0;
}