import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;

class main {

  static class StringTrie<A> {

    A value;

    TreeMap<String, StringTrie<A>> children;

    StringTrie() {
    }

    StringTrie(A value) {
      this.value = value;
    }

    void makeCaseInsensitive() {
      children = asCIMap(children);
    }

    boolean isCaseInsensitive() {
      return isCIMap(children);
    }

    void put(String string, A value) {
      add(string, value);
    }

    void add(String string, A value) {
      if (empty(string)) {
        this.value = value;
        return;
      }
      String existingPrefix = isCaseInsensitive() ? longestCommonPrefixOfCISetAndString(string, navigableKeys(children)) : longestCommonPrefixOfNavigableSetAndString(string, navigableKeys(children));
      if (nempty(existingPrefix)) {
        StringTrie<A> child = children.get(existingPrefix);
        String substring = substring(string, l(existingPrefix));
        if (child != null) {
          child.add(substring, value);
          return;
        }
        StringTrie<A> branch = newChild(null);
        if (branch.children == null)
          branch.children = new TreeMap();
        Map.Entry<String, StringTrie<A>> e = children.higherEntry(existingPrefix);
        String key = e.getKey();
        child = e.getValue();
        children.remove(e.getKey());
        children.put(existingPrefix, branch);
        branch.children.put(substring(key, l(existingPrefix)), child);
        branch.children.put(substring, newChild(value));
        return;
      }
      if (children == null)
        children = new TreeMap();
      children.put(string, newChild(value));
    }

    Map<String, A> asMap() {
      Map<String, A> map = isCaseInsensitive() ? ciMap() : new TreeMap();
      StringBuilder buf = new StringBuilder();
      collectMap(buf, map);
      return map;
    }

    private void collectMap(StringBuilder buf, Map<String, A> map) {
      if (value != null)
        map.put(str(buf), value);
      int n = l(buf);
      for (Map.Entry<String, StringTrie<A>> __1 : _entrySet(children)) {
        String string = __1.getKey();
        StringTrie<A> child = __1.getValue();
        buf.append(string);
        child.collectMap(buf, map);
        buf.setLength(n);
      }
    }

    public String toString() {
      StringBuilder buf = new StringBuilder();
      if (value != null) {
        buf.append("\"\" => ").append(value).append("\n");
        childrenToString(buf, 2);
      } else
        childrenToString(buf, 0);
      return str(buf);
    }

    void toString(StringBuilder buf, int indent) {
      if (value != null)
        buf.append(" => ").append(value);
      buf.append("\n");
      childrenToString(buf, indent + 2);
    }

    void childrenToString(StringBuilder buf, int indent) {
      for (Map.Entry<String, StringTrie<A>> __0 : _entrySet(children)) {
        String string = __0.getKey();
        StringTrie<A> child = __0.getValue();
        buf.append(spaces(indent)).append(quote(string));
        child.toString(buf, indent);
      }
    }

    private StringTrie<A> newChild(A value) {
      StringTrie<A> child = new StringTrie<>(value);
      if (isCaseInsensitive())
        child.makeCaseInsensitive();
      return child;
    }

    Set<String> childStrings() {
      return keys(children);
    }

    StringTrie<A> getChild(String string) {
      return children.get(string);
    }

    NavigableMap<String, StringTrie<A>> children() {
      return children;
    }
  }

  static <B> TreeMap<String, B> asCIMap(Map<String, B> map) {
    return asCaseInsensitiveMap(map);
  }

  static boolean isCIMap(Map m) {
    return m instanceof TreeMap && ((TreeMap) m).comparator() == caseInsensitiveComparator();
  }

  static boolean empty(Collection c) {
    return c == null || c.isEmpty();
  }

  static boolean empty(Iterable c) {
    return c == null || !c.iterator().hasNext();
  }

  static boolean empty(CharSequence s) {
    return s == null || s.length() == 0;
  }

  static boolean empty(Map map) {
    return map == null || map.isEmpty();
  }

  static boolean empty(Object[] o) {
    return o == null || o.length == 0;
  }

  static boolean empty(Iterator i) {
    return i == null || !i.hasNext();
  }

  static boolean empty(double[] a) {
    return a == null || a.length == 0;
  }

  static boolean empty(float[] a) {
    return a == null || a.length == 0;
  }

  static boolean empty(int[] a) {
    return a == null || a.length == 0;
  }

  static boolean empty(long[] a) {
    return a == null || a.length == 0;
  }

  static boolean empty(byte[] a) {
    return a == null || a.length == 0;
  }

  static boolean empty(short[] a) {
    return a == null || a.length == 0;
  }

  static boolean empty(File f) {
    return getFileSize(f) == 0;
  }

  static String longestCommonPrefixOfCISetAndString(String s, NavigableSet<String> set) {
    if (set == null || s == null)
      return null;
    String a = set.floor(s), b = set.higher(s);
    int n = Math.max(lCommonPrefixCI(a, s), lCommonPrefixCI(b, s));
    return takeFirst_string(s, n);
  }

  static <A, B> NavigableSet<A> navigableKeys(NavigableMap<A, B> map) {
    return map == null ? new TreeSet() : map.navigableKeySet();
  }

  static String longestCommonPrefixOfNavigableSetAndString(String s, NavigableSet<String> set) {
    if (set == null || s == null)
      return null;
    String a = set.floor(s), b = set.higher(s);
    int n1 = lCommonPrefix(a, s), n2 = lCommonPrefix(b, s);
    int n = Math.max(n1, n2);
    return takeFirst_string(s, n);
  }

  static boolean nempty(Collection c) {
    return !empty(c);
  }

  static boolean nempty(CharSequence s) {
    return !empty(s);
  }

  static boolean nempty(Object[] o) {
    return !empty(o);
  }

  static boolean nempty(byte[] o) {
    return !empty(o);
  }

  static boolean nempty(int[] o) {
    return !empty(o);
  }

  static boolean nempty(Map m) {
    return !empty(m);
  }

  static boolean nempty(Iterator i) {
    return i != null && i.hasNext();
  }

  static String substring(String s, int x) {
    return substring(s, x, strL(s));
  }

  static String substring(String s, int x, int y) {
    if (s == null)
      return null;
    if (x < 0)
      x = 0;
    int n = s.length();
    if (y < x)
      y = x;
    if (y > n)
      y = n;
    if (x >= y)
      return "";
    return s.substring(x, y);
  }

  static String substring(String s, CharSequence l) {
    return substring(s, l(l));
  }

  static int l(Object[] a) {
    return a == null ? 0 : a.length;
  }

  static int l(boolean[] a) {
    return a == null ? 0 : a.length;
  }

  static int l(byte[] a) {
    return a == null ? 0 : a.length;
  }

  static int l(short[] a) {
    return a == null ? 0 : a.length;
  }

  static int l(long[] a) {
    return a == null ? 0 : a.length;
  }

  static int l(int[] a) {
    return a == null ? 0 : a.length;
  }

  static int l(float[] a) {
    return a == null ? 0 : a.length;
  }

  static int l(double[] a) {
    return a == null ? 0 : a.length;
  }

  static int l(char[] a) {
    return a == null ? 0 : a.length;
  }

  static int l(Collection c) {
    return c == null ? 0 : c.size();
  }

  static int l(Iterator i) {
    return iteratorCount_int_close(i);
  }

  static int l(Map m) {
    return m == null ? 0 : m.size();
  }

  static int l(CharSequence s) {
    return s == null ? 0 : s.length();
  }

  static long l(File f) {
    return f == null ? 0 : f.length();
  }

  static <A> TreeMap<String, A> ciMap() {
    return caseInsensitiveMap();
  }

  static String str(Object o) {
    return o == null ? "null" : o.toString();
  }

  static String str(char[] c) {
    return new String(c);
  }

  static <A, B> Set<Map.Entry<A, B>> _entrySet(Map<A, B> map) {
    return map == null ? Collections.EMPTY_SET : map.entrySet();
  }

  static String spaces(int n) {
    return rep(' ', n);
  }

  static String quote(Object o) {
    if (o == null)
      return "null";
    return quote(str(o));
  }

  static String quote(String s) {
    if (s == null)
      return "null";
    StringBuilder out = new StringBuilder((int) (l(s) * 1.5 + 2));
    quote_impl(s, out);
    return out.toString();
  }

  static void quote_impl(String s, StringBuilder out) {
    out.append('"');
    int l = s.length();
    for (int i = 0; i < l; i++) {
      char c = s.charAt(i);
      if (c == '\\' || c == '"')
        out.append('\\').append(c);
      else if (c == '\r')
        out.append("\\r");
      else if (c == '\n')
        out.append("\\n");
      else if (c == '\t')
        out.append("\\t");
      else if (c == '\0')
        out.append("\\0");
      else
        out.append(c);
    }
    out.append('"');
  }

  static <A, B> Set<A> keys(Map<A, B> map) {
    return map == null ? new HashSet() : map.keySet();
  }

  static Set keys(Object map) {
    return keys((Map) map);
  }

  static <B> TreeMap<String, B> asCaseInsensitiveMap(Map<String, B> map) {
    if (isCIMap(map))
      return (TreeMap) map;
    TreeMap<String, B> m = ciMap();
    putAll(m, map);
    return m;
  }

  static Comparator<String> caseInsensitiveComparator() {
    return betterCIComparator();
  }

  static long getFileSize(String path) {
    return path == null ? 0 : new File(path).length();
  }

  static long getFileSize(File f) {
    return f == null ? 0 : f.length();
  }

  static int lCommonPrefixCI(String a, String b) {
    return lCommonPrefixIC(a, b);
  }

  static String takeFirst_string(int n, String s) {
    return substring(s, 0, n);
  }

  static String takeFirst_string(String s, int n) {
    return substring(s, 0, n);
  }

  static int lCommonPrefix(String a, String b) {
    int i = 0, n = Math.min(l(a), l(b));
    while (i < n && a.charAt(i) == b.charAt(i)) ++i;
    return i;
  }

  static int strL(String s) {
    return s == null ? 0 : s.length();
  }

  static <A> int iteratorCount_int_close(Iterator<A> i) {
    try {
      int n = 0;
      if (i != null)
        while (i.hasNext()) {
          i.next();
          ++n;
        }
      if (i instanceof AutoCloseable)
        ((AutoCloseable) i).close();
      return n;
    } catch (Exception __e) {
      throw rethrow(__e);
    }
  }

  static <A> TreeMap<String, A> caseInsensitiveMap() {
    return new TreeMap(caseInsensitiveComparator());
  }

  static String rep(int n, char c) {
    return repeat(c, n);
  }

  static String rep(char c, int n) {
    return repeat(c, n);
  }

  static <A> List<A> rep(A a, int n) {
    return repeat(a, n);
  }

  static <A> List<A> rep(int n, A a) {
    return repeat(n, a);
  }

  static <A, B> Map<A, B> putAll(Map<A, B> a, Map<? extends A, ? extends B> b) {
    if (a != null && b != null)
      a.putAll(b);
    return a;
  }

  static betterCIComparator_C betterCIComparator_instance;

  static betterCIComparator_C betterCIComparator() {
    if (betterCIComparator_instance == null)
      betterCIComparator_instance = new betterCIComparator_C();
    return betterCIComparator_instance;
  }

  final static class betterCIComparator_C implements Comparator<String> {

    public int compare(String s1, String s2) {
      if (s1 == null)
        return s2 == null ? 0 : -1;
      if (s2 == null)
        return 1;
      int n1 = s1.length();
      int n2 = s2.length();
      int min = Math.min(n1, n2);
      for (int i = 0; i < min; i++) {
        char c1 = s1.charAt(i);
        char c2 = s2.charAt(i);
        if (c1 != c2) {
          c1 = Character.toUpperCase(c1);
          c2 = Character.toUpperCase(c2);
          if (c1 != c2) {
            c1 = Character.toLowerCase(c1);
            c2 = Character.toLowerCase(c2);
            if (c1 != c2) {
              return c1 - c2;
            }
          }
        }
      }
      return n1 - n2;
    }
  }

  static int lCommonPrefixIC(String a, String b) {
    int i = 0, n = Math.min(l(a), l(b));
    while (i < n && eqic(a.charAt(i), b.charAt(i))) ++i;
    return i;
  }

  static RuntimeException rethrow(Throwable t) {
    throw t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
  }

  static RuntimeException rethrow(String msg, Throwable t) {
    throw new RuntimeException(msg, t);
  }

  static String repeat(char c, int n) {
    n = Math.max(n, 0);
    char[] chars = new char[n];
    for (int i = 0; i < n; i++) chars[i] = c;
    return new String(chars);
  }

  static <A> List<A> repeat(A a, int n) {
    n = Math.max(n, 0);
    List<A> l = new ArrayList(n);
    for (int i = 0; i < n; i++) l.add(a);
    return l;
  }

  static <A> List<A> repeat(int n, A a) {
    return repeat(a, n);
  }

  static boolean eqic(String a, String b) {
    if ((a == null) != (b == null))
      return false;
    if (a == null)
      return true;
    return a.equalsIgnoreCase(b);
  }

  static boolean eqic(char a, char b) {
    if (a == b)
      return true;
    char u1 = Character.toUpperCase(a);
    char u2 = Character.toUpperCase(b);
    if (u1 == u2)
      return true;
    return Character.toLowerCase(u1) == Character.toLowerCase(u2);
  }

  static boolean eq(Object a, Object b) {
    return a == b || a != null && b != null && a.equals(b);
  }

  static String asString(Object o) {
    return o == null ? null : o.toString();
  }
}