import java.util.HashSet;

public class TrieImpl {

	public TrieImpl() {
		root = null;
	}

	private static int R = 33; // alphabet size
	private Node root;

	private static class Node {
		private HashSet<Integer> val;
		private Node[] next = new Node[R];
	}

	public HashSet<Integer> get(String key) {
		Node x = get(root, key, 0);
		if (x == null) return null;
		return (HashSet<Integer>) x.val;
	}
	private Node get(Node x, String key, int d) {
		if (x == null) return null;
		if (d == key.length()) return x;
		char c = key.charAt(d);
		return get(x.next[charIndex(c)], key, d+1);
	}
	public void put(String key, int val) {
		root = put(root, key, val, 0);
	}
	private Node put(Node x, String key, int val, int d) {
		if (x == null) x = new Node();
		if (d == key.length()) {
			if (null != x.val) { x.val.add(val); }
			else {
				x.val = new HashSet<Integer>();
				x.val.add(val);
			}
			return x;
		}
		char c = key.charAt(d);
		x.next[charIndex(c)] = put(x.next[charIndex(c)], key, val, d+1);
		return x;
	}
	private int charIndex(char c) {
		if(c >= 'а' && c <= 'е') return c - 'а';
		else if (c >= 'ж' && c <= 'я') return c - 'а' + 1;
		else if (c == 'ё') return 'ж' - 'а';
		return 0;
	}
}