class PatriciaTree<T> {
    class Node<T> {
        public Node(String key, int bitPos, Node succ) {
            m_Key = key;
            m_BitPos = bitPos;
            boolean blsRight = (key.charAt(0) & (1 << bitPos)) != 0;
            m_Left = new Node(blsRight ? succ : this);
            m_Right = new Node(blsRight ? this : succ);
        }
        public Node(String key, int bitPos) {
            this(key,bitPos,null);
        }
        public Node(Node succ) {
            this("",0,succ);
        }
        public int getNrOfMatchingChars(String key) {
            int nrOfMatchingChars = 0;
            while (nrOfMatchingChars < m_Key.length() && nrOfMatchingChars < this.m_Key.length()) {
                if (m_Key.charAt(nrOfMatchingChars) != this.m_Key.charAt(nrOfMatchingChars)) {
                  break;
                }
                nrOfMatchingChars++;
            }
            return nrOfMatchingChars;
        }

        public String m_Key;
        public int m_BitPos;
        public Node m_Left;
        public Node m_Right;
    }

    public boolean search(String s) {
        Node node = m_Root;
        int lastBitPos = -1;
        String newS = "";
        while (node != null && lastBitPos < node.m_BitPos) {
            lastBitPos = node.m_BitPos;
            int i = node.getNrOfMatchingChars(s);
            node = (newS.charAt(i+1) & (1 << node.m_BitPos)) != 0 ? node.m_Right : node.m_Left;
        }
        return node != null && node.m_Key == s;
    }

    public void insert(String key, T value) {
        Node node = m_Root;
        int lastBitPos = -1;
        String newStr = "";
        while (node != null && lastBitPos < node.m_BitPos) {
            lastBitPos = node.m_BitPos;
            int i = node.getNrOfMatchingChars(key);
            newStr = key.substring(i,node.m_Key.length());
            node = (newStr.charAt(0) & (1 << node.m_BitPos)) != 0 ? node.m_Right : node.m_Left;
        }
        if (node == null) {
            node = new Node(key,lastBitPos+1);
        } else if (newStr.charAt(0) != node.m_Key.charAt(node.getNrOfMatchingChars(key)+1)) {
            int i = 0;
            while
        }
    }

    private Node m_Root = new Node("",-1,null);
}

public class u11a1 {
    public static void main(String[] args) {
        PatriciaTree pt = new PatriciaTree();
    }
}