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 String longPseudoMultiSetToLines(Map map) {
List l = new ArrayList();
if (map != null) for (A o : keysSortedByValueDesc(map))
l.add(map.get(o) + ": " + str(o));
return lines(l);
}
static List keysSortedByValueDesc(final Map map) {
return keysSortedByValuesDesc(map);
}
static String str(Object o) {
return o == null ? "null" : o.toString();
}
static String str(char[] c) {
return new String(c);
}
static String lines(Iterable lines) { return fromLines(lines); }
static String lines(Object[] lines) { return fromLines(asList(lines)); }
static List lines(String s) { return toLines(s); }
static List keysSortedByValuesDesc(final Map map) {
List l = new ArrayList(map.keySet());
sort(l, mapComparatorDesc(map));
return l;
}
// usually L
static String fromLines(Iterable lines) {
StringBuilder buf = new StringBuilder();
if (lines != null)
for (Object line : lines)
buf.append(str(line)).append('\n');
return buf.toString();
}
static String fromLines(String... lines) {
return fromLines(asList(lines));
}
static ArrayList asList(A[] a) {
return a == null ? new ArrayList() : new ArrayList(Arrays.asList(a));
}
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(float[] a) {
if (a == null) return null;
ArrayList l = emptyList(a.length);
for (float i : a) l.add(i);
return l;
}
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;
}
static IterableIterator toLines(File f) {
return linesFromFile(f);
}
static List toLines(String s) {
List lines = new ArrayList();
if (s == null) return lines;
int start = 0;
while (true) {
int i = toLines_nextLineBreak(s, start);
if (i < 0) {
if (s.length() > start) lines.add(s.substring(start));
break;
}
lines.add(s.substring(start, i));
if (s.charAt(i) == '\r' && i+1 < s.length() && s.charAt(i+1) == '\n')
i += 2;
else
++i;
start = i;
}
return lines;
}
static int toLines_nextLineBreak(String s, int start) {
for (int i = start; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '\r' || c == '\n')
return i;
}
return -1;
}
static void sort(T[] a, Comparator super T> c) {
Arrays.sort(a, c);
}
static void sort(T[] a) {
Arrays.sort(a);
}
static void sort(List a, Comparator super T> c) {
Collections.sort(a, c);
}
static void sort(List a) {
Collections.sort(a);
}
static Comparator mapComparatorDesc(final Map map) {
return new Comparator() {
public int compare(A a, A b) {
return cmp(map.get(b), map.get(a));
}
};
}
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 CloseableIterableIterator linesFromFile(File f) { try {
if (!f.exists()) return emptyCloseableIterableIterator();
if (ewic(f.getName(), ".gz"))
return linesFromReader(utf8bufferedReader(newGZIPInputStream(f)));
return linesFromReader(utf8bufferedReader(f));
} catch (Exception __e) { throw rethrow(__e); } }
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(Object a, Object b) {
if (a == null) return b == null ? 0 : -1;
if (b == null) return 1;
return ((Comparable) a).compareTo(b);
}
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 int max(Collection c) {
int x = Integer.MIN_VALUE;
for (int i : c) x = max(x, i);
return 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 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(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 int l(Object o) {
return o == null ? 0
: o instanceof String ? l((String) o)
: o instanceof Map ? l((Map) o)
: o instanceof Collection ? l((Collection) o)
: o instanceof Object[] ? l((Object[]) o)
: o instanceof boolean[] ? l((boolean[]) o)
: o instanceof byte[] ? l((byte[]) o)
: o instanceof char[] ? l((char[]) o)
: o instanceof short[] ? l((short[]) o)
: o instanceof int[] ? l((int[]) o)
: o instanceof float[] ? l((float[]) o)
: o instanceof double[] ? l((double[]) o)
: o instanceof long[] ? l((long[]) o)
: (Integer) call(o, "size");
}
static CloseableIterableIterator emptyCloseableIterableIterator_instance = new CloseableIterableIterator() {
public Object next() { throw fail(); }
public boolean hasNext() { return false; }
};
static CloseableIterableIterator emptyCloseableIterableIterator() {
return emptyCloseableIterableIterator_instance;
}
static boolean ewic(String a, String b) {
return endsWithIgnoreCase(a, b);
}
static CloseableIterableIterator linesFromReader(Reader r) {
final BufferedReader br = bufferedReader(r);
return iteratorFromFunction_f0_autoCloseable(new F0() { String get() { try { return readLineFromReaderWithClose(br); } catch (Exception __e) { throw rethrow(__e); } }
public String toString() { return "ret readLineFromReaderWithClose(br);"; }}, _wrapIOCloseable(r));
}
static BufferedReader utf8bufferedReader(InputStream in) { try {
return bufferedReader(_registerIOWrap(new InputStreamReader(in, "UTF-8"), in));
} catch (Exception __e) { throw rethrow(__e); } }
static BufferedReader utf8bufferedReader(File f) { try {
return utf8bufferedReader(newFileInputStream(f));
} catch (Exception __e) { throw rethrow(__e); } }
static GZIPInputStream newGZIPInputStream(File f) {
return gzInputStream(f);
}
static GZIPInputStream newGZIPInputStream(InputStream in) {
return gzInputStream(in);
}
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 Object call(Object o) {
return callF(o);
}
// varargs assignment fixer for a single string array argument
static Object call(Object o, String method, String[] arg) {
return call(o, method, new Object[] {arg});
}
static Object call(Object o, String method, Object... args) {
//ret call_cached(o, method, args);
return call_withVarargs(o, method, args);
}
static RuntimeException fail() { throw new RuntimeException("fail"); }
static RuntimeException fail(Throwable e) { throw asRuntimeException(e); }
static RuntimeException fail(Object msg) { throw new RuntimeException(String.valueOf(msg)); }
static RuntimeException fail(String msg) { throw new RuntimeException(msg == null ? "" : msg); }
static RuntimeException fail(String msg, Throwable innerException) { throw new RuntimeException(msg, innerException); }
static boolean endsWithIgnoreCase(String a, String b) {
int la = l(a), lb = l(b);
return la >= lb && regionMatchesIC(a, la-lb, b, 0, lb);
}
static BufferedReader bufferedReader(Reader r) {
return r instanceof BufferedReader ? (BufferedReader) r : _registerIOWrap(new BufferedReader(r), r);
}
static CloseableIterableIterator iteratorFromFunction_f0_autoCloseable(final F0 f, final AutoCloseable closeable) {
class IFF2 extends CloseableIterableIterator {
A a;
boolean done;
public boolean hasNext() {
getNext();
return !done;
}
public A next() {
getNext();
if (done) throw fail();
A _a = a;
a = null;
return _a;
}
void getNext() {
if (done || a != null) return;
a = f.get();
done = a == null;
}
public void close() throws Exception {
if (closeable != null) closeable.close();
}
};
return new IFF2();
}
static String readLineFromReaderWithClose(BufferedReader r) { try {
String s = r.readLine();
if (s == null) r.close();
return s;
} catch (Exception __e) { throw rethrow(__e); } }
static AutoCloseable _wrapIOCloseable(final AutoCloseable c) {
return c == null ? null : new AutoCloseable() { public String toString() { return "c.close();\r\n _registerIO(c, null, false);"; } public void close() throws Exception {
c.close();
_registerIO(c, null, false);
}};
}
static A _registerIOWrap(A wrapper, Object wrapped) {
return wrapper;
}
static FileInputStream newFileInputStream(File path) throws IOException {
return newFileInputStream(path.getPath());
}
static FileInputStream newFileInputStream(String path) throws IOException {
FileInputStream f = new FileInputStream(path);
_registerIO(f, path, true);
return f;
}
static int gzInputStream_defaultBufferSize = 65536;
static GZIPInputStream gzInputStream(File f) { try {
return gzInputStream(new FileInputStream(f));
} catch (Exception __e) { throw rethrow(__e); } }
static GZIPInputStream gzInputStream(File f, int bufferSize) { try {
return gzInputStream(new FileInputStream(f), bufferSize);
} catch (Exception __e) { throw rethrow(__e); } }
static GZIPInputStream gzInputStream(InputStream in) {
return gzInputStream(in, gzInputStream_defaultBufferSize);
}
static GZIPInputStream gzInputStream(InputStream in, int bufferSize) { try {
return _registerIOWrap(new GZIPInputStream(in, gzInputStream_defaultBufferSize), in);
} catch (Exception __e) { throw rethrow(__e); } }
static void _handleError(Error e) {
call(javax(), "_handleError", e);
}
static Map> callF_cache = newDangerousWeakHashMap();
static A callF(F0 f) {
return f == null ? null : f.get();
}
static void callF(VF1 f, A a) {
if (f != null) f.get(a);
}
static Object callF(Object f, Object... args) { try {
if (f instanceof String)
return callMC((String) f, args);
if (f instanceof Runnable) {
((Runnable) f).run();
return null;
}
if (f == null) return null;
Class c = f.getClass();
ArrayList methods;
synchronized(callF_cache) {
methods = callF_cache.get(c);
if (methods == null)
methods = callF_makeCache(c);
}
int n = l(methods);
if (n == 0) {
throw fail("No get method in " + getClassName(c));
}
if (n == 1) return invokeMethod(methods.get(0), f, args);
for (int i = 0; i < n; i++) {
Method m = methods.get(i);
if (call_checkArgs(m, args, false))
return invokeMethod(m, f, args);
}
throw fail("No matching get method in " + getClassName(c));
} catch (Exception __e) { throw rethrow(__e); } }
// used internally
static ArrayList callF_makeCache(Class c) {
ArrayList l = new ArrayList();
Class _c = c;
do {
for (Method m : _c.getDeclaredMethods())
if (m.getName().equals("get")) {
m.setAccessible(true);
l.add(m);
}
if (!l.isEmpty()) break;
_c = _c.getSuperclass();
} while (_c != null);
callF_cache.put(c, l);
return l;
}
static Object call_withVarargs(Object o, String method, Object... args) { try {
if (o == null) return null;
if (o instanceof Class) {
Class c = (Class) o;
_MethodCache cache = callOpt_getCache(c);
Method me = cache.findStaticMethod(method, args);
if (me != null)
return invokeMethod(me, null, args);
// try varargs
List methods = cache.cache.get(method);
if (methods != null) methodSearch: for (Method m : methods) {
{ if (!(m.isVarArgs())) continue; }
{ if (!(isStaticMethod(m))) continue; }
Object[] newArgs = massageArgsForVarArgsCall(m, args);
if (newArgs != null)
return invokeMethod(m, null, newArgs);
}
throw fail("Method " + c.getName() + "." + method + "(" + joinWithComma(classNames(args)) + ") not found");
} else {
Class c = o.getClass();
_MethodCache cache = callOpt_getCache(c);
Method me = cache.findMethod(method, args);
if (me != null)
return invokeMethod(me, o, args);
// try varargs
List methods = cache.cache.get(method);
if (methods != null) methodSearch: for (Method m : methods) {
{ if (!(m.isVarArgs())) continue; }
Object[] newArgs = massageArgsForVarArgsCall(m, args);
if (newArgs != null)
return invokeMethod(m, o, newArgs);
}
throw fail("Method " + c.getName() + "." + method + "(" + joinWithComma(classNames(args)) + ") not found in " + c);
}
} catch (Exception __e) { throw rethrow(__e); } }
static RuntimeException asRuntimeException(Throwable t) {
if (t instanceof Error)
_handleError((Error) t);
return t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
}
static boolean regionMatchesIC(String a, int offsetA, String b, int offsetB, int len) {
return a != null && a.regionMatches(true, offsetA, b, offsetB, len);
}
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;
if (x >= s.length()) return "";
if (y < x) y = x;
if (y > s.length()) y = s.length();
return s.substring(x, y);
}
static void _registerIO(Object object, String path, boolean opened) {
}
static Class javax() {
return getJavaX();
}
static Map newDangerousWeakHashMap() {
return _registerDangerousWeakMap(synchroMap(new WeakHashMap()));
}
// initFunction: voidfunc(Map) - is called initially, and after clearing the map
static Map newDangerousWeakHashMap(Object initFunction) {
return _registerDangerousWeakMap(synchroMap(new WeakHashMap()), initFunction);
}
static HashMap> callMC_cache = new HashMap();
static String callMC_key;
static Method callMC_value;
// varargs assignment fixer for a single string array argument
static Object callMC(String method, String[] arg) {
return callMC(method, new Object[] {arg});
}
static Object callMC(String method, Object... args) { try {
Method me;
if (callMC_cache == null) callMC_cache = new HashMap(); // initializer time workaround
synchronized(callMC_cache) {
me = method == callMC_key ? callMC_value : null;
}
if (me != null) try {
return invokeMethod(me, null, args);
} catch (IllegalArgumentException e) {
throw new RuntimeException("Can't call " + me + " with arguments " + classNames(args), e);
}
List m;
synchronized(callMC_cache) {
m = callMC_cache.get(method);
}
if (m == null) {
if (callMC_cache.isEmpty()) {
callMC_makeCache();
m = callMC_cache.get(method);
}
if (m == null) throw fail("Method named " + method + " not found in main");
}
int n = m.size();
if (n == 1) {
me = m.get(0);
synchronized(callMC_cache) {
callMC_key = method;
callMC_value = me;
}
try {
return invokeMethod(me, null, args);
} catch (IllegalArgumentException e) {
throw new RuntimeException("Can't call " + me + " with arguments " + classNames(args), e);
}
}
for (int i = 0; i < n; i++) {
me = m.get(i);
if (call_checkArgs(me, args, false))
return invokeMethod(me, null, args);
}
throw fail("No method called " + method + " with matching arguments found in main");
} catch (Exception __e) { throw rethrow(__e); } }
static void callMC_makeCache() {
synchronized(callMC_cache) {
callMC_cache.clear();
Class _c = (Class) mc(), c = _c;
while (c != null) {
for (Method m : c.getDeclaredMethods())
if ((m.getModifiers() & java.lang.reflect.Modifier.STATIC) != 0) {
m.setAccessible(true);
multiMapPut(callMC_cache, m.getName(), m);
}
c = c.getSuperclass();
}
}
}
static String getClassName(Object o) {
return o == null ? "null" : o instanceof Class ? ((Class) o).getName() : o.getClass().getName();
}
static Object invokeMethod(Method m, Object o, Object... args) { try {
try {
return m.invoke(o, args);
} catch (InvocationTargetException e) {
throw rethrow(getExceptionCause(e));
} catch (IllegalArgumentException e) {
throw new IllegalArgumentException(e.getMessage() + " - was calling: " + m + ", args: " + joinWithSpace(classNames(args)));
}
} catch (Exception __e) { throw rethrow(__e); } }
static boolean call_checkArgs(Method m, Object[] args, boolean debug) {
Class>[] types = m.getParameterTypes();
if (types.length != args.length) {
if (debug)
print("Bad parameter length: " + args.length + " vs " + types.length);
return false;
}
for (int i = 0; i < types.length; i++) {
Object arg = args[i];
if (!(arg == null ? !types[i].isPrimitive()
: isInstanceX(types[i], arg))) {
if (debug)
print("Bad parameter " + i + ": " + arg + " vs " + types[i]);
return false;
}
}
return true;
}
static final Map callOpt_cache = newDangerousWeakHashMap();
static Object callOpt_cached(Object o, String methodName, Object... args) { try {
if (o == null) return null;
if (o instanceof Class) {
Class c = (Class) o;
_MethodCache cache = callOpt_getCache(c);
// TODO: (super-rare) case where method exists static and non-static
// with different args
Method me = cache.findMethod(methodName, args);
if (me == null || (me.getModifiers() & Modifier.STATIC) == 0) return null;
return invokeMethod(me, null, args);
} else {
Class c = o.getClass();
_MethodCache cache = callOpt_getCache(c);
Method me = cache.findMethod(methodName, args);
if (me == null) return null;
return invokeMethod(me, o, args);
}
} catch (Exception __e) { throw rethrow(__e); } }
static _MethodCache callOpt_getCache(Class c) {
synchronized(callOpt_cache) {
_MethodCache cache = callOpt_cache.get(c);
if (cache == null)
callOpt_cache.put(c, cache = new _MethodCache(c));
return cache;
}
}
static boolean isStaticMethod(Method m) {
return methodIsStatic(m);
}
static Object[] massageArgsForVarArgsCall(Method m, Object[] args) {
Class>[] types = m.getParameterTypes();
int n = types.length-1, nArgs = args.length;
if (nArgs < n) return null;
for (int i = 0; i < n; i++)
if (!argumentCompatibleWithType(args[i], types[i]))
return null;
Class varArgType = types[n].getComponentType();
for (int i = n; i < nArgs; i++)
if (!argumentCompatibleWithType(args[i], varArgType))
return null;
Object[] newArgs = new Object[n+1];
arraycopy(args, 0, newArgs, 0, n);
Object[] varArgs = arrayOfType(varArgType, nArgs-n);
arraycopy(args, n, varArgs, 0, nArgs-n);
newArgs[n] = varArgs;
return newArgs;
}
static String joinWithComma(Collection c) {
return join(", ", c);
}
static String joinWithComma(String... c) {
return join(", ", c);
}
static String joinWithComma(Pair p) {
return p == null ? "" : joinWithComma(str(p.a), str(p.b));
}
static List classNames(Collection l) {
return getClassNames(l);
}
static List classNames(Object[] l) {
return getClassNames(Arrays.asList(l));
}
static int strL(String s) {
return s == null ? 0 : s.length();
}
static Class __javax;
static Class getJavaX() { try {
return __javax;
} catch (Exception __e) { throw rethrow(__e); } }
static List _registerDangerousWeakMap_preList;
static A _registerDangerousWeakMap(A map) {
return _registerDangerousWeakMap(map, null);
}
static A _registerDangerousWeakMap(A map, Object init) {
callF(init, map);
if (init instanceof String) {
final String f = (String) init;
init = new VF1