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 java.util.function.*; 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 java.awt.geom.*; import javax.imageio.*; import java.math.*; import java.time.Duration; import java.lang.invoke.VarHandle; import java.lang.invoke.MethodHandles; class main { static String shortenToFirstAndLast(int chars, String s) { if (s == null) return ""; return s.length() <= chars*2 ? s : takeFirst(chars, s) + "..." + takeLast(chars, s); } static List takeFirst(List l, int n) { return l(l) <= n ? l : newSubListOrSame(l, 0, n); } static List takeFirst(int n, List l) { return takeFirst(l, n); } static String takeFirst(int n, String s) { return substring(s, 0, n); } static String takeFirst(String s, int n) { return substring(s, 0, n); } static CharSequence takeFirst(int n, CharSequence s) { return subCharSequence(s, 0, n); } static List takeFirst(int n, Iterator it) { if (it == null) return null; List l = new ArrayList(); for (int _repeat_0 = 0; _repeat_0 < n; _repeat_0++) { if (it.hasNext()) l.add(it.next()); else break; } return l; } static List takeFirst(int n, Iterable i) { if (i == null) return null; return i == null ? null : takeFirst(n, i.iterator()); } static List takeFirst(int n, IterableIterator i) { return takeFirst(n, (Iterator) i); } static int[] takeFirst(int n, int[] a) { return takeFirstOfIntArray(n, a); } static short[] takeFirst(int n, short[] a) { return takeFirstOfShortArray(n, a); } static byte[] takeFirst(int n, byte[] a) { return takeFirstOfByteArray(n, a); } static byte[] takeFirst(byte[] a, int n) { return takeFirstOfByteArray(n, a); } static double[] takeFirst(int n, double[] a) { return takeFirstOfDoubleArray(n, a); } static double[] takeFirst(double[] a, int n) { return takeFirstOfDoubleArray(n, a); } static Map takeFirst(int n, Map map) { return takeFirstFromMap(n, map); } static List takeLast(List l, int n) { return newSubList(l, l(l)-n); } static List takeLast(int n, List l) { return takeLast(l, n); } static String takeLast(int n, String s) { return substring(s, l(s)-n); } static String takeLast(String s, int n) { return substring(s, l(s)-n); } 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); } // consumes the iterator && closes it if possible 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 List newSubListOrSame(List l, int startIndex) { return newSubListOrSame(l, startIndex, l(l)); } static List newSubListOrSame(List l, int startIndex, int endIndex) { if (l == null) return null; int n = l(l); startIndex = max(0, startIndex); endIndex = min(n, endIndex); if (startIndex >= endIndex) return ll(); if (startIndex == 0 && endIndex == n) return l; return cloneList(l.subList(startIndex, endIndex)); } 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); } // convenience method for quickly dropping a prefix static String substring(String s, CharSequence l) { return substring(s, lCharSequence(l)); } static CharSequence subCharSequence(CharSequence s, int x) { return subCharSequence(s, x, s == null ? 0 : s.length()); } static CharSequence subCharSequence(CharSequence s, int x, int y) { if (s == null) return null; if (x < 0) x = 0; if (x >= s.length()) return ""; if (y < x) y = x; if (y > s.length()) y = s.length(); return s.subSequence(x, y); } static int[] takeFirstOfIntArray(int[] b, int n) { return subIntArray(b, 0, n); } static int[] takeFirstOfIntArray(int n, int[] b) { return takeFirstOfIntArray(b, n); } static short[] takeFirstOfShortArray(short[] b, int n) { return subShortArray(b, 0, n); } static short[] takeFirstOfShortArray(int n, short[] b) { return takeFirstOfShortArray(b, n); } static byte[] takeFirstOfByteArray(byte[] b, int n) { return subByteArray(b, 0, n); } static byte[] takeFirstOfByteArray(int n, byte[] b) { return takeFirstOfByteArray(b, n); } static double[] takeFirstOfDoubleArray(double[] b, int n) { return subDoubleArray(b, 0, n); } static double[] takeFirstOfDoubleArray(int n, double[] b) { return takeFirstOfDoubleArray(b, n); } static Map takeFirstFromMap(int n, Map map) { if (map == null) return null; Map map2 = similarEmptyMap(map); if (n > 0) for (Map.Entry e : map.entrySet()) if (n-- <= 0) break; else map2.put(e.getKey(), e.getValue()); return map2; } static List newSubList(List l, int startIndex, int endIndex) { return cloneList(subList(l, startIndex, endIndex)); } static List newSubList(List l, int startIndex) { return cloneList(subList(l, startIndex)); } static int iteratorCount_int_close(Iterator 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 int max(int a, int b) { return Math.max(a, b); } static int max(int a, int b, int c) { return max(max(a, b), c); } static long max(int a, long b) { return Math.max((long) a, b); } static long max(long a, long b) { return Math.max(a, b); } static double max(int a, double b) { return Math.max((double) a, b); } static float max(float a, float b) { return Math.max(a, b); } static double max(double a, double b) { return Math.max(a, b); } static > A max (Iterable l) { A max = null; var it = iterator(l); if (it.hasNext()) { max = it.next(); while (it.hasNext()) { A a = it.next(); if (cmp(a, max) > 0) max = a; } } return max; } /*Nah. static int max(Collection c) { int x = Integer.MIN_VALUE; for (int i : c) x = max(x, i); ret x; }*/ static double max(double[] c) { if (c.length == 0) return Double.MIN_VALUE; double x = c[0]; for (int i = 1; i < c.length; i++) x = Math.max(x, c[i]); return x; } static float max(float[] c) { if (c.length == 0) return Float.MAX_VALUE; float x = c[0]; for (int i = 1; i < c.length; i++) x = Math.max(x, c[i]); return x; } static byte max(byte[] c) { byte x = -128; for (byte d : c) if (d > x) x = d; return x; } static short max(short[] c) { short x = -0x8000; for (short d : c) if (d > x) x = d; return x; } static int max(int[] c) { int x = Integer.MIN_VALUE; for (int d : c) if (d > x) x = d; return x; } static > A max(A a, A b) { return cmp(a, b) >= 0 ? 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 > A min(A a, A b) { return cmp(a, b) <= 0 ? a : b; } static List ll(A... a) { ArrayList l = new ArrayList(a.length); if (a != null) for (A x : a) l.add(x); return l; } static ArrayList cloneList(Iterable l) { return l instanceof Collection ? cloneList((Collection) l) : asList(l); } static ArrayList cloneList(Collection l) { if (l == null) return new ArrayList(); synchronized(collectionMutex(l)) { return new ArrayList(l); } } static int strL(String s) { return s == null ? 0 : s.length(); } static int lCharSequence(CharSequence s) { return s == null ? 0 : s.length(); } static int[] subIntArray(int[] b, int start) { return subIntArray(b, start, l(b)); } static int[] subIntArray(int[] b, int start, int end) { start = max(start, 0); end = min(end, l(b)); if (start == 0 && end == l(b)) return b; if (start >= end) return new int[0]; int[] x = new int[end-start]; System.arraycopy(b, start, x, 0, end-start); return x; } static short[] subShortArray(short[] b, int start, int end) { start = max(start, 0); end = min(end, l(b)); if (start == 0 && end == l(b)) return b; if (start >= end) return new short[0]; short[] x = new short[end-start]; System.arraycopy(b, start, x, 0, end-start); return x; } static byte[] subByteArray(byte[] b, int start) { return subByteArray(b, start, l(b)); } static byte[] subByteArray(byte[] b, int start, int end) { start = max(start, 0); end = min(end, l(b)); if (start == 0 && end == l(b)) return b; if (start >= end) return new byte[0]; byte[] x = new byte[end-start]; System.arraycopy(b, start, x, 0, end-start); return x; } static double[] subDoubleArray(double[] b, int start) { return subDoubleArray(b, start, l(b)); } static double[] subDoubleArray(double[] b, int start, int end) { start = max(start, 0); end = min(end, l(b)); if (start == 0 && end == l(b)) return b; if (start >= end) return new double[0]; double[] x = new double[end-start]; System.arraycopy(b, start, x, 0, end-start); return x; } static Map similarEmptyMap(Map m) { if (m instanceof TreeMap) return new TreeMap(((TreeMap) m).comparator()); if (m instanceof LinkedHashMap) return new LinkedHashMap(); // default to a hash map return new HashMap(); } static Map similarEmptyMap(Iterable m) { if (m instanceof TreeSet) return new TreeMap(((TreeSet) m).comparator()); if (m instanceof LinkedHashSet) return new LinkedHashMap(); return new HashMap(); } static List subList(List l, int startIndex) { return subList(l, startIndex, l(l)); } static List subList(int startIndex, List l) { return subList(l, startIndex); } static List subList(int startIndex, int endIndex, List l) { return subList(l, startIndex, endIndex); } static List subList(List l, int startIndex, int endIndex) { if (l == null) return null; int n = l(l); startIndex = Math.max(0, startIndex); endIndex = Math.min(n, endIndex); if (startIndex > endIndex) return ll(); if (startIndex == 0 && endIndex == n) return l; return l.subList(startIndex, endIndex); } static RuntimeException rethrow(Throwable t) { if (t instanceof Error) _handleError((Error) t); throw t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t); } static RuntimeException rethrow(String msg, Throwable t) { throw new RuntimeException(msg, t); } static Iterator iterator(Iterable c) { return c == null ? emptyIterator() : c.iterator(); } static int cmp(Number a, Number b) { return a == null ? b == null ? 0 : -1 : cmp(a.doubleValue(), b.doubleValue()); } static int cmp(double a, double b) { return a < b ? -1 : a == b ? 0 : 1; } static int cmp(int a, int b) { return a < b ? -1 : a == b ? 0 : 1; } static int cmp(long a, long b) { return a < b ? -1 : a == b ? 0 : 1; } static int cmp(Object a, Object b) { if (a == null) return b == null ? 0 : -1; if (b == null) return 1; return ((Comparable) a).compareTo(b); } // unclear semantics as to whether return null on null static ArrayList asList(A[] a) { return a == null ? new ArrayList() : new ArrayList(Arrays.asList(a)); } static ArrayList asList(char[] a) { if (a == null) return null; ArrayList l = emptyList(a.length); for (var i : a) l.add(i); return l; } static ArrayList asList(byte[] a) { if (a == null) return null; ArrayList l = emptyList(a.length); for (var i : a) l.add(i); return l; } static ArrayList asList(int[] a) { if (a == null) return null; ArrayList l = emptyList(a.length); for (int i : a) l.add(i); return l; } static ArrayList asList(long[] a) { if (a == null) return null; ArrayList l = emptyList(a.length); for (long i : a) l.add(i); return l; } static ArrayList asList(float[] a) { if (a == null) return null; ArrayList l = emptyList(a.length); for (float i : a) l.add(i); return l; } static ArrayList asList(double[] a) { if (a == null) return null; ArrayList l = emptyList(a.length); for (double i : a) l.add(i); return l; } static ArrayList asList(short[] a) { if (a == null) return null; ArrayList l = emptyList(a.length); for (short i : a) l.add(i); return l; } static ArrayList asList(Iterator it) { ArrayList l = new ArrayList(); if (it != null) while (it.hasNext()) l.add(it.next()); return l; } // disambiguation static ArrayList asList(IterableIterator s) { return asList((Iterator) s); } static ArrayList asList(Iterable s) { if (s instanceof ArrayList) return (ArrayList) s; ArrayList l = new ArrayList(); if (s != null) for (A a : s) l.add(a); return l; } static ArrayList asList(Enumeration e) { ArrayList l = new ArrayList(); if (e != null) while (e.hasMoreElements()) l.add(e.nextElement()); return l; } // TODO: JDK 17!! ?? No! Yes? Yes!! static Object collectionMutex(List l) { return l; } static Object collectionMutex(Object o) { if (o instanceof List) return o; // TODO: actually use our own maps so we can get the mutex properly String c = className(o); return o; } static void _handleError(Error e) { //call(javax(), '_handleError, e); } static Iterator emptyIterator() { return Collections.emptyIterator(); } static ArrayList emptyList() { return new ArrayList(); //ret Collections.emptyList(); } static ArrayList emptyList(int capacity) { return new ArrayList(max(0, capacity)); } // Try to match capacity static ArrayList emptyList(Iterable l) { return l instanceof Collection ? emptyList(((Collection) l).size()) : emptyList(); } static ArrayList emptyList(Object[] l) { return emptyList(l(l)); } // get correct type at once static ArrayList emptyList(Class c) { return new ArrayList(); } static String className(Object o) { return getClassName(o); } static String getClassName(Object o) { return o == null ? "null" : o instanceof Class ? ((Class) o).getName() : o.getClass().getName(); } // you still need to implement hasNext() and next() static abstract class IterableIterator implements Iterator, Iterable { public Iterator iterator() { return this; } public void remove() { unsupportedOperation(); } } static UnsupportedOperationException unsupportedOperation() { throw new UnsupportedOperationException(); } }