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;
// A represents the return type of the backtrackable main computation
import java.awt.geom.*;
import static x30_pkg.x30_util.DynamicObject;
import java.nio.file.Path;
import java.text.*;
import java.text.NumberFormat;
import java.nio.charset.Charset;
import java.util.TimeZone;
import java.text.SimpleDateFormat;
class main {
static class BStack extends VStack implements IBStack {
static int idCounter;
int stackID = ++idCounter; // for debugging
// alternative to backtrack to
BStack alternative;
// steps to undo before switching to the alternative
List undos;
BStack() {}
BStack(Computable computation) { push(computation); }
BStack(Iterable l) { pushAll(l); }
static class NoOptionsException extends RuntimeException {}
BStack cloneStack() {
BStack s = new BStack();
s.alternative = alternative;
s.undos = undos;
undos = null;
s.stack = shallowCloneElements(stack);
return s;
}
public void addUndo(AutoCloseable undo) {
if (undo == null) return;
if (undos == null) undos = new ArrayList();
undos.add(undo);
}
public void options(B function,
IVF1... options) {
options(function, asList(options));
}
public void options(B function, Iterable> options) {
List> optionsList = nonNulls(options);
if (empty(optionsList))
throw new NoOptionsException();
// All options except first are stored as alternatives
// in cloned stacks.
for (int i = l(optionsList)-1; i > 0; i--)
setAlternative(optionsList.get(i));
// Execute the first option
first(optionsList).get(function);
}
static class ExecuteOption implements VStack.Computable , IFieldsToList{
IVF1 option;
ExecuteOption() {}
ExecuteOption(IVF1 option) {
this.option = option;}
public String toString() { return shortClassName_dropNumberPrefix(this) + "(" + option + ")"; }public Object[] _fieldsToList() { return new Object[] {option}; }
public void step(VStack stack, Object subComputationResult) {
Object target = stack.caller();
stack._return();
option.get(target);
}
}
void setAlternative(IVF1 option) {
alternative = cloneStack();
alternative.push(new ExecuteOption(option));
}
// Try to backtrack one step and return a new stack
// Returns null if no backtracking possible
public BStack backtrack() { try {
// Apply undos in reverse order
for (int i = l(undos)-1; i >= 0; i--)
undos.get(i).close();
return alternative;
} catch (Exception __e) { throw rethrow(__e); } }
public A nextResult() {
stepAll(this);
return (A) latestResult;
}
// calculate next result and print stack at every step
public A nextResultWithPrintStruct(long maxSteps) {
stepMaxWithPrintIndentedStruct(this, maxSteps);
return (A) latestResult;
}
}
static List shallowCloneElements(List l) {
return lmap(__22 -> shallowClone(__22), l);
}
static Concept options(List l) {
return l(l) == 1 ? first(l) : new Options(l);
}
// 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(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(Producer p) {
ArrayList l = new ArrayList();
A a;
if (p != null) while ((a = p.next()) != null)
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 ArrayList asList(ReverseChain c) {
return c == null ? emptyList() : c.toList();
}
static List asList(Pair p) {
return p == null ? null : ll(p.a, p.b);
}
static List nonNulls(Iterable l) {
return withoutNulls(l);
}
static List nonNulls(A[] l) {
return withoutNulls(l);
}
static Map nonNulls(Map map) {
return withoutNulls(map);
}
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(BitSet bs) { return bs == null || bs.isEmpty(); }
static boolean empty(Object o) {
if (o instanceof Collection) return empty((Collection) o);
if (o instanceof String) return empty((String) o);
if (o instanceof Map) return empty((Map) o);
if (o instanceof Object[]) return empty((Object[]) o);
if (o instanceof byte[]) return empty((byte[]) o);
if (o == null) return true;
throw fail("unknown type for 'empty': " + getType(o));
}
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(MultiSet ms) { return ms == null || ms.isEmpty(); }
static boolean empty(IMultiMap mm) { return mm == null || mm.size() == 0; }
static boolean empty(File f) { return getFileSize(f) == 0; }
static boolean empty(Rect r) { return !(r != null && r.w != 0 && r.h != 0); }
static boolean empty(Chain c) { return c == null; }
static boolean empty(AppendableChain c) { return c == null; }
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 int l(MultiSet ms) { return ms == null ? 0 : ms.size(); }
static int l(IMultiMap mm) { return mm == null ? 0 : mm.size(); }
static int l(AppendableChain a) { return a == null ? 0 : a.size; }
static Object first(Object list) {
return first((Iterable) list);
}
static A first(List list) {
return empty(list) ? null : list.get(0);
}
static A first(A[] bla) {
return bla == null || bla.length == 0 ? null : bla[0];
}
static Pair first(Map map) {
return mapEntryToPair(first(entrySet(map)));
}
static Pair first(MultiMap mm) {
if (mm == null) return null;
var e = first(mm.data.entrySet());
if (e == null) return null;
return pair(e.getKey(), first(e.getValue()));
}
static A first(IterableIterator i) {
return first((Iterator) i);
}
static A first(Iterator i) {
return i == null || !i.hasNext() ? null : i.next();
}
static A first(Iterable i) {
if (i == null) return null;
Iterator it = i.iterator();
return it.hasNext() ? it.next() : null;
}
static Character first(String s) { return empty(s) ? null : s.charAt(0); }
static Character first(CharSequence s) { return empty(s) ? null : s.charAt(0); }
static A first(Pair p) {
return p == null ? null : p.a;
}
static A first(T3 t) {
return t == null ? null : t.a;
}
static Byte first(byte[] l) {
return empty(l) ? null : l[0];
}
static A first(A[] l, IF1 pred) {
return firstThat(l, pred);
}
static A first(Iterable l, IF1 pred) {
return firstThat(l, pred);
}
static A first(IF1 pred, Iterable l) {
return firstThat(pred, l);
}
static A first(AppendableChain a) {
return a == null ? null : a.element;
}
static String shortClassName_dropNumberPrefix(Object o) {
return dropNumberPrefix(shortClassName(o));
}
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);
}
// returns number of steps
static long stepAll(Steppable s) {
long steps = 0;
if (s != null) {
var pingSource = pingSource();
while (true) {
ping(pingSource);
if (s.step())
++steps;
else
break;
}
}
return steps;
}
static void stepMaxWithPrintIndentedStruct(long maxSteps, Steppable s) {
if (s == null) return;
String struct = null;
long steps = 0;
do {
if (steps++ > maxSteps) break;
print(struct = indentedStruct(s));
} while (s.step());
String struct2 = indentedStruct(s);
if (!eq(struct, struct2)) print(struct2);
}
static void stepMaxWithPrintIndentedStruct(Steppable s, long maxSteps) {
stepMaxWithPrintIndentedStruct(maxSteps, s);
}
static List lmap(IF1 f, Iterable l) {
return lambdaMap(f, l);
}
static List lmap(IF1 f, A[] l) {
return lambdaMap(f, l);
}
static A shallowClone(A o) {
return (A) shallowClone_impl(o);
}
static A shallowClone(A o, A emptyClone) {
return copyFields(o, emptyClone);
}
static Object shallowClone_impl(Object o) {
if (o == null)
return o;
if (o instanceof List)
return cloneList((List) o);
if (o instanceof Map) return cloneMap((Map) o);
if (o instanceof String || o instanceof Number || o instanceof Boolean)
return o;
if (o instanceof Object[]) {
Object[] l = (Object[]) o;
return l.clone();
}
// clone an arbitrary custom object
Object clone;
if (o instanceof IMakeEmptyClone)
clone = ((IMakeEmptyClone) o).makeEmptyClone();
else
clone = nuEmptyObject(o.getClass());
//print("Cloning custom: " + o);
copyFields(o, clone);
return clone;
}
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 List ll(A... a) {
ArrayList l = new ArrayList(a.length);
if (a != null) for (A x : a) l.add(x);
return l;
}
static List withoutNulls(Iterable l) {
if (l instanceof List)
if (!containsNulls((List) l)) return ((List) l);
List l2 = new ArrayList();
for (A a : l)
if (a != null)
l2.add(a);
return l2;
}
static Map withoutNulls(Map map) {
Map map2 = similarEmptyMap(map);
for (A a : keys(map))
if (a != null) {
B b = map.get(a);
if (b != null)
map2.put(a, b);
}
return map2;
}
static List withoutNulls(A[] l) {
List l2 = new ArrayList();
if (l != null) for (A a : l)
if (a != null)
l2.add(a);
return l2;
}
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(Object... objects) { throw new Fail(objects); }
static RuntimeException fail(String msg) { throw new RuntimeException(msg == null ? "" : msg); }
static RuntimeException fail(String msg, Throwable innerException) { throw new RuntimeException(msg, innerException); }
static String getType(Object o) {
return getClassName(o);
}
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 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 Pair mapEntryToPair(Map.Entry e) {
return e == null ? null : pair(e.getKey(), e.getValue());
}
static Set> entrySet(Map map) {
return _entrySet(map);
}
static Pair pair(A a, B b) {
return new Pair(a, b);
}
static Pair pair(A a) {
return new Pair(a, a);
}
static A firstThat(Iterable l, IF1 pred) {
for (A a : unnullForIteration(l))
if (pred.get(a))
return a;
return null;
}
static A firstThat(A[] l, IF1 pred) {
for (A a : unnullForIteration(l))
if (pred.get(a))
return a;
return null;
}
static A firstThat(IF1 pred, Iterable l) {
return firstThat(l, pred);
}
static A firstThat(IF1 pred, A[] l) {
return firstThat(l, pred);
}
static String dropNumberPrefix(String s) {
return dropFirst(s, indexOfNonDigit(s));
}
static String shortClassName(Object o) {
if (o == null) return null;
Class c = o instanceof Class ? (Class) o : o.getClass();
String name = c.getName();
return shortenClassName(name);
}
static void _handleError(Error e) {
//call(javax(), '_handleError, e);
}
// assumptions:
// -pingSource() stays constant within a stack frame (so you can cache it)
// -all changes happen with tempSetPingSource
// -multiple threads can share a PingSource
static PingSource pingSource() {
return pingSource_tl().get();
}
static PingSource pingSource(Thread thread) {
return pingSource_tl().get(thread);
}
// legacy mode
//sbool ping_actions_shareable = true;
static volatile boolean ping_pauseAll = false;
static int ping_sleep = 100; // poll pauseAll flag every 100
static volatile boolean ping_anyActions = false;
static Map ping_actions = newWeakHashMap();
static ThreadLocal ping_isCleanUpThread = new ThreadLocal();
// ignore pingSource if not PingV3
static boolean ping(PingSource pingSource) { return ping(); }
// always returns true
static boolean ping() {
//ifdef useNewPing
newPing();
//endifdef
if (ping_pauseAll || ping_anyActions) ping_impl(true /* XXX */);
//ifndef LeanMode ping_impl(); endifndef
return true;
}
// returns true when it slept
static boolean ping_impl(boolean okInCleanUp) { try {
if (ping_pauseAll && !isAWTThread()) {
do
Thread.sleep(ping_sleep);
while (ping_pauseAll);
return true;
}
if (ping_anyActions) { // don't allow sharing ping_actions
if (!okInCleanUp && !isTrue(ping_isCleanUpThread.get()))
failIfUnlicensed();
Object action = null;
synchronized(ping_actions) {
if (!ping_actions.isEmpty()) {
action = ping_actions.get(currentThread());
if (action instanceof Runnable)
ping_actions.remove(currentThread());
if (ping_actions.isEmpty()) ping_anyActions = false;
}
}
if (action instanceof Runnable)
((Runnable) action).run();
else if (eq(action, "cancelled"))
throw fail("Thread cancelled.");
}
return false;
} catch (Exception __e) { throw rethrow(__e); } }
static volatile StringBuffer local_log = new StringBuffer(); // not redirected
static boolean printAlsoToSystemOut = true;
static volatile Appendable print_log = local_log; // might be redirected, e.g. to main bot
// in bytes - will cut to half that
static volatile int print_log_max = 1024*1024;
static volatile int local_log_max = 100*1024;
static boolean print_silent = false; // total mute if set
static Object print_byThread_lock = new Object();
static volatile ThreadLocal