/**

 * A character tree map.

 */

static class Trie<T> {

  private final char start;

  private final Trie<T>[] arr;

  public final T value;

  private Trie(char start, Trie<T>[] arr, @Nullable T value) {

    this.start = start;

    this.arr = arr;

    this.value = value;

  }

  @Nullable Trie<T> get(char ch) {

    int i = ch - start;

    return 0 <= i && i < arr.length ? arr[i] : null;

  }

  @Nullable Trie<T> getIgnoreCase(char ch) {

    int i = lower(ch) - start;

    return 0 <= i && i < arr.length ? arr[i] : null;

  }

  /**

   * Returns the value corresponding to s[off:end].

   */

  @Nullable T get(String s, int off, int end) {

    Trie<T> t = this;

    while (off < end) {

      t = t.get(s.charAt(off++));

      if (t == null) { return null; }

    }

    return t.value;

  }

  @Nullable T get(char[] s, int off, int end) {

    Trie<T> t = this;

    while (off < end) {

      t = t.get(s[off++]);

      if (t == null) { return null; }

    }

    return t.value;

  }

  /**

   * Returns the value corresponding to s[off:end] ignoring the case of ASCII

   * characters and matching only against lowercase keys.

   */

  @Nullable T getIgnoreCase(String s, int off, int end) {

    Trie<T> t = this;

    while (off < end) {

      t = t.getIgnoreCase(s.charAt(off++));

      if (t == null) { return null; }

    }

    return t.value;

  }

  @Nullable T getIgnoreCase(char[] s, int off, int end) {

    Trie<T> t = this;

    while (off < end) {

      t = t.getIgnoreCase(s[off++]);

      if (t == null) { return null; }

    }

    return t.value;

  }

  @Override

  public String toString() {

    StringBuilder sb = new StringBuilder();

    toString(sb, 0);

    return sb.toString();

  }

  private void toString(StringBuilder sb, int depth) {

    sb.append(value).append(" {");

    ++depth;

    for (int i = 0; i < arr.length; ++i) {

      if (arr[i] == null) { continue; }

      sb.append('\n');

      for (int j = depth; --j >= 0;) { sb.append("  "); }

      sb.append('\'').append((char) (i + start)).append("':");

      arr[i].toString(sb, depth);

    }

    sb.append("}");

  }

  static <A> Builder<A> builder() { return new Builder<A>(null, (char) 0); }

  static final class Builder<A> {

    A value;

    final char ch;

    final List<Builder<A>> children = new ArrayList<Builder<A>>();

    Builder(@Nullable A value, char ch) {

      this.value = value;

      this.ch = ch;

    }

    Builder<A> put(String s, @Nullable A newValue) {

      put(this, s, newValue);

      return this;

    }

    static <A> void put(Builder<A> b, String s, @Nullable A newValue) {

      for (int i = 0, n = s.length(); i < n; ++i) {

        char ch = s.charAt(i);

        Builder<A> next = null;

        for (Builder<A> child : b.children) {

          if (child.ch == ch) {

            next = child;

            break;

          }

        }

        if (next == null) {

          next = new Builder<A>(null, ch);

          b.children.add(next);

        }

        b = next;

      }

      b.value = newValue;

    }

    @SuppressWarnings("unchecked")

    Trie<A> build() {

      Trie<A>[] arr;

      int n = children.size();

      char min = 0;

      if (n == 0) {

        arr = (Trie<A>[]) NO_TRIES;

      } else {

        Collections.sort(children, new Comparator<Builder<?>>() {

            public int compare(Builder<?> a, Builder<?> b) {

              return a.ch - b.ch;

            }

          });

        min = children.get(0).ch;

        int max = children.get(n-1).ch;

        arr = (Trie<A>[]) new Trie<?>[max - min + 1];

        for (int i = 0; i < n; ++i) {

          Builder<A> b = children.get(i);

          arr[b.ch - min] = b.build();

        }

      }

      return new Trie<A>(min, arr, value);

    }

  }

  private static final Trie<?>[] NO_TRIES = new Trie<?>[0];

}