/**
 * 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];
}