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 TreeMap litAlphaNumMap(Object... x) {
  TreeMap map = new TreeMap (alphaNumComparator());
  litmap_impl(map, x);
  return map;
}
static AlphanumComparator alphaNumComparator_instance;

static Comparator<String> alphaNumComparator() {
  if (alphaNumComparator_instance == null)
    alphaNumComparator_instance = new AlphanumComparator();
  return alphaNumComparator_instance;
}


static HashMap litmap(Object... x) {
  HashMap map = new HashMap();
  litmap_impl(map, x);
  return map;
}

static void litmap_impl(Map map, Object... x) {
  if (x != null) for (int i = 0; i < x.length-1; i += 2)
    if (x[i+1] != null)
      map.put(x[i], x[i+1]);
}



/*
 * The Alphanum Algorithm is an improved sorting algorithm for strings
 * containing numbers.  Instead of sorting numbers in ASCII order like
 * a standard sort, this algorithm sorts numbers in numeric order.
 *
 * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
 *
 * Released under the MIT License - https://opensource.org/licenses/MIT
 *
 * Copyright 2007-2017 David Koelle
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
 * USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

/**
 * This is an updated version with enhancements made by Daniel Migowski,
 * Andre Bogus, and David Koelle. Updated by David Koelle in 2017.
 */
 
static class AlphanumComparator implements Comparator<String> {
  boolean ignoreCase = false;
  
  private final boolean isDigit(char ch) {
    return ((ch >= 48) && (ch <= 57));
  }

  /** Length of string is passed in for improved efficiency (only need to calculate it once) **/
  private final String getChunk(String s, int slength, int marker) {
    StringBuilder chunk = new StringBuilder();
    char c = s.charAt(marker);
    chunk.append(c);
    marker++;
    if (isDigit(c))
        while (marker < slength) {
            c = s.charAt(marker);
            if (!isDigit(c))
                break;
            chunk.append(c);
            marker++;
        }
    else
        while (marker < slength) {
            c = s.charAt(marker);
            if (isDigit(c))
                break;
            chunk.append(c);
            marker++;
        }
    return chunk.toString();
  }

  public int compare(String s1, String s2) {
  	if (s1 == null) return s2 == null ? 0 : -1;
    if (s2 == null) return 1;

    int thisMarker = 0;
    int thatMarker = 0;
    int s1Length = s1.length();
    int s2Length = s2.length();

    while (thisMarker < s1Length && thatMarker < s2Length) {
      String thisChunk = getChunk(s1, s1Length, thisMarker);
      thisMarker += thisChunk.length();

      String thatChunk = getChunk(s2, s2Length, thatMarker);
      thatMarker += thatChunk.length();

      // If both chunks contain numeric characters, sort them numerically
      int result = 0;
      if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0)))
      {
          // Simple chunk comparison by length.
          int thisChunkLength = thisChunk.length();
          result = thisChunkLength - thatChunk.length();
          // If equal, the first different number counts
          if (result == 0)
          {
              for (int i = 0; i < thisChunkLength; i++)
              {
                  result = thisChunk.charAt(i) - thatChunk.charAt(i);
                  if (result != 0)
                  {
                      return result;
                  }
              }
          }
      } 
      else
      {
          result = thisChunk.compareTo(thatChunk);
      }

      if (result != 0)
          return result;
    }
    
    return s1Length - s2Length;
  }
}

static boolean isDigit(char c) {
  return Character.isDigit(c);
}


}