
public class TernarySearchTrie {
	public Node root;

	public void put(String s, int val) {
		this.root = this.put(this.root, s, 0, val);
	}
	private Node put(Node r, String s, int val) {
		if (r == null) {
			r = new Node();
			if (s.length() > 0)
				r.middleChar = s.charAt(0);
		}

		if (s.length() == 0) {
			r.val = val;
		} else {
			if (r.middleChar == s.charAt(0)) {
				r.middle = put(r.middle, s.substring(1) val);
			} else if (r.middleChar < s.charAt(0)) {
				r.right = put(r.right, s, val);
			} else {
				r.left = put(r.left, s, val);
			}
		}
		return r;
	}

	public int get(String s) {
		Node x = this.get(this.root, s, 0);
		if (x == null) return -1;
		return x.val;
	}

	private Node get(Node r, String s) {
		if (r == null)
			return null;

		if (s.length() == 0) {
			return r;
		}

		char c = s.charAt(0);
		if (c == r.middleChar) {
			return get(r.middle, s.substring(1));
		else if (c < r.middleChar) {
			return get(r.left, s);
		} else {
			return get(r.right, s);
		}
	}
}


class Node {
	public int val;
	char middleChar;
	Node left;
	Node right;
	Node middle;
}