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 int levenWithSwapsSubstringIC(String haystack, String needle) { int m = strL(needle), n = strL(haystack); // base cases if (containsIgnoreCase(haystack, needle)) return 0; int[] vx = new int[n+1], v0 = new int[n+1], v1 = new int[n+1]; for (int i = 0; i < m; i++) { // iterate over needle v1[0] = i+1; for (int j = 0; j < n; j++) { // iterate over haystack int cost = neqic(needle.charAt(i), haystack.charAt(j)) ? 1 : 0; int d = min3(v1[j]+1, // insertion v0[j+1]+1, // deletion v0[j]+cost); // substitution if (i > 0 && j > 0 && equalsIgnoreCase(needle.charAt(i), haystack.charAt(j-1)) && equalsIgnoreCase(needle.charAt(i-1), haystack.charAt(j))) d = min(d, vx[j-1] + 1); // transposition v1[j+1] = d; } int[] temp = vx; vx = v0; v0 = v1; v1 = temp; } return minOfIntArray(v0); } static int strL(String s) { return s == null ? 0 : s.length(); } static boolean containsIgnoreCase(Collection l, String s) { if (l != null) for (String x : l) if (eqic(x, s)) return true; return false; } static boolean containsIgnoreCase(String[] l, String s) { if (l != null) for (String x : l) if (eqic(x, s)) return true; return false; } static boolean containsIgnoreCase(String s, char c) { return indexOfIgnoreCase(s, String.valueOf(c)) >= 0; } static boolean containsIgnoreCase(String a, String b) { return indexOfIgnoreCase(a, b) >= 0; } static boolean neqic(String a, String b) { return !eqic(a, b); } static boolean neqic(char a, char b) { return !eqic(a, b); } static int min3(int a, int b, int c) { return min(min(a, b), c); } static boolean equalsIgnoreCase(String a, String b) { return eqic(a, b); } static boolean equalsIgnoreCase(char a, char b) { return eqic(a, b); } static int min(int a, int b) { return Math.min(a, b); } static long min(long a, long b) { return Math.min(a, b); } static float min(float a, float b) { return Math.min(a, b); } static float min(float a, float b, float c) { return min(min(a, b), c); } static double min(double a, double b) { return Math.min(a, b); } static double min(double[] c) { double x = Double.MAX_VALUE; for (double d : c) x = Math.min(x, d); return x; } static float min(float[] c) { float x = Float.MAX_VALUE; for (float d : c) x = Math.min(x, d); return x; } static byte min(byte[] c) { byte x = 127; for (byte d : c) if (d < x) x = d; return x; } static short min(short[] c) { short x = 0x7FFF; for (short d : c) if (d < x) x = d; return x; } static int min(int[] c) { int x = Integer.MAX_VALUE; for (int d : c) if (d < x) x = d; return x; } static int minOfIntArray(int[] a) { if (a == null || a.length == 0) return 0; int n = a.length, x = a[0]; for (int i = 1; i < n; i++) x = min(a[i], x); return x; } 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); } // works on lists and strings and null static int indexOfIgnoreCase(List a, String b) { return indexOfIgnoreCase(a, b, 0); } static int indexOfIgnoreCase(List a, String b, int i) { int n = a == null ? 0 : a.size(); for (; i < n; i++) if (eqic(a.get(i), b)) return i; return -1; } static int indexOfIgnoreCase(String a, String b) { return indexOfIgnoreCase_manual(a, b); /*Matcher m = Pattern.compile(b, Pattern.CASE_INSENSITIVE + Pattern.LITERAL).matcher(a); if (m.find()) return m.start(); else ret -1;*/ } static boolean eq(Object a, Object b) { return a == b || (a == null ? b == null : b != null && a.equals(b)); } static String asString(Object o) { return o == null ? null : o.toString(); } static int indexOfIgnoreCase_manual(String a, String b) { int la = strL(a), lb = strL(b); if (la < lb) return -1; int n = la-lb; loop: for (int i = 0; i <= n; i++) { for (int j = 0; j < lb; j++) { char c1 = a.charAt(i+j), c2 = b.charAt(j); if (!eqic(c1, c2)) continue loop; } return i; } return -1; } static String str(Object o) { return o == null ? "null" : o.toString(); } static String str(char[] c) { return new String(c); } }