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;
// This backtracking-enabled stack (BStack) postpones cloning stack
// frames as long as possible.
// More specifically, only the current top frame is actually mutable.
// Some stack frames below (from 0 up to clonePointer) may not be
// cloned yet, and are cloned (=made mutable) by the pop() function.
// The tests (test_BStack_v3) pass, but they might not test the lazy
// cloning. So for safety, stick with BStack_v2 until there are more
// tests for BStack_v3.
// 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_v3 extends VStack implements IBStack {
static int idCounter;
int stackID = ++idCounter; // for debugging
// elements at this index and below must be cloned before use
int clonePointer = -1;
// cloned version made at last branch point
BStack_v3 snapshot;
// remaining options at last branch point
Iterator options;
// steps to undo before switching to the alternative
List undos;
BStack_v3() {}
BStack_v3(Computable computation) { push(computation); }
BStack_v3(Iterable l) { pushAll(l); }
BStack_v3 cloneStack() {
BStack_v3 s = new BStack_v3();
s.snapshot = snapshot;
s.options = options;
s.undos = undos;
undos = null;
s.stack = cloneList(stack);
// Directly clone current function, clone older stack entries
// lazily.
replaceLast(s.stack, shallowClone(last(stack)));
clonePointer = l(stack)-2;
return s;
}
public void addUndo(AutoCloseable undo) {
if (undo == null || snapshot == null) return;
if (undos == null) undos = new ArrayList();
undos.add(undo);
}
public void options(B function, IVF1... options) {
options(function, arrayIterator(options));
}
public void options(B function, Iterable> options) {
Iterator> iterator = nonNullIterator(iterator(options));
if (!iterator.hasNext())
throw new NoOptionsException();
IVF1 firstOption = iterator.next();
// All options except first are stored as alternatives
// in cloned stacks.
setOptions(iterator);
// Execute the first option
firstOption.get(function);
}
void setOptions(Iterator> options) {
snapshot = cloneStack();
this.options = (Iterator) options;
}
// Try to backtrack one step and return a new stack
// Returns null if no backtracking possible
public BStack_v3 backtrack() { try {
// Apply undos in reverse order
for (int i = l(undos)-1; i >= 0; i--)
undos.get(i).close();
// no more options? done
if (options == null || !options.hasNext()) return null;
// get snapshot and option to execute
BStack_v3 nextStack = snapshot;
var option = options.next();
// If there are more options in the list, make another clone
// of the snapshot
boolean moreOptions = options.hasNext();
if (moreOptions) {
nextStack = new BStack_v3();
nextStack.stack = shallowCloneElements(snapshot.stack);
nextStack.snapshot = snapshot;
nextStack.options = options;
}
nextStack.push(new ExecuteOption(option));
return nextStack;
} 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;
}
protected void pop() { super.pop();
int idx = l(stack)-1;
// Clone the new top stack frame if necessary
if (idx >= 0 && idx == clonePointer) {
stack.set(idx, shallowClone(stack.get(idx)));
--clonePointer;
}
}
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);
}
}
static class NoOptionsException extends RuntimeException {}
}
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 void replaceLast(List l, A a) {
replaceLastElement(l, a);
}
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 A last(List l) {
return empty(l) ? null : l.get(l.size()-1);
}
static char last(String s) {
return empty(s) ? '#' : s.charAt(l(s)-1);
}
static byte last(byte[] a) {
return l(a) != 0 ? a[l(a)-1] : 0;
}
static int last(int[] a) {
return l(a) != 0 ? a[l(a)-1] : 0;
}
static double last(double[] a) {
return l(a) != 0 ? a[l(a)-1] : 0;
}
static A last(A[] a) {
return l(a) != 0 ? a[l(a)-1] : null;
}
static A last(Iterator it) {
A a = null;
while (it.hasNext()) { ping(); a = it.next(); }
return a;
}
static A last(Collection l) {
if (l == null) return null;
if (l instanceof List) return (A) last((List) l);
if (l instanceof SortedSet) return (A) last((SortedSet) l);
Iterator it = iterator(l);
A a = null;
while (it.hasNext()) { ping(); a = it.next(); }
return a;
}
static A last(SortedSet l) {
return l == null ? null : l.last();
}
static A last(ReverseChain l) {
return l == null ? null : l.element;
}
static A last(CompactLinkedHashSet set) {
return set == null ? null : set.last();
}
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 Concept options(List l) {
return l(l) == 1 ? first(l) : new Options(l);
}
static IterableIterator arrayIterator(A[] l) {
return l == null ? null : new IterableIterator() {
int i = 0;
public boolean hasNext() { return i < l.length; }
public A next() { return l[i++]; }
};
}
static IterableIterator nonNullIterator(Iterator it) {
return notNulls_iterator(it);
}
static Iterator iterator(Iterable c) {
return c == null ? emptyIterator() : c.iterator();
}
static List shallowCloneElements(List l) {
return lmap(__22 -> shallowClone(__22), l);
}
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 String shortClassName_dropNumberPrefix(Object o) {
return dropNumberPrefix(shortClassName(o));
}
// 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);
}
// 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 replaceLastElement(List l, A a) {
if (nempty(l))
l.set(l(l)-1, a);
}
static A copyFields(Object x, A y, String... fields) {
if (empty(fields)) { // assume we should copy all fields
Map map = objectToMap(x);
for (String field : map.keySet())
setOpt(y, field, map.get(field));
} else
for (String field : fields) {
Object o = getOpt(x, field);
if (o != null)
setOpt(y, field, o);
}
return y;
}
static A copyFields(Object x, A y, Collection fields) {
return copyFields(x, y, asStringArray(fields));
}
static Map cloneMap(Map map) {
if (map == null) return new HashMap();
// assume mutex is equal to map
synchronized(map) {
return map instanceof TreeMap ? new TreeMap((TreeMap) map) // copies comparator
: map instanceof LinkedHashMap ? new LinkedHashMap(map)
: new HashMap(map);
}
}
static List cloneMap(Iterable l, IF1 f) {
List x = emptyList(l);
if (l != null) for (A o : cloneList(l))
x.add(f.get(o));
return x;
}
static Map nuEmptyObject_cache = newDangerousWeakHashMap();
static A nuEmptyObject(Class c) { try {
Constructor ctr;
synchronized(nuEmptyObject_cache) {
ctr = nuEmptyObject_cache.get(c);
if (ctr == null) {
nuEmptyObject_cache.put(c, ctr = nuEmptyObject_findConstructor(c));
makeAccessible(ctr);
}
}
try {
return (A) ctr.newInstance();
} catch (InstantiationException e) {
if (empty(e.getMessage()))
if ((c.getModifiers() & Modifier.ABSTRACT) != 0)
throw fail("Can't instantiate abstract class " + className(c), e);
else
throw fail("Can't instantiate " + className(c), e);
else throw rethrow(e);
}
} catch (Exception __e) { throw rethrow(__e); } }
static Constructor nuEmptyObject_findConstructor(Class c) {
for (Constructor m : getDeclaredConstructors_cached(c))
if (m.getParameterTypes().length == 0)
return m;
throw fail("No default constructor declared in " + c.getName());
}
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; }
// 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 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 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 IterableIterator notNulls_iterator(Iterator it) {
return filterIterator(it, new F1() { public Boolean get(A a) { try { return a != null; } catch (Exception __e) { throw rethrow(__e); } }
public String toString() { return "a != null"; }});
}
static Iterator emptyIterator() {
return Collections.emptyIterator();
}
static List lmap(IF1 f, Iterable l) {
return lambdaMap(f, l);
}
static List lmap(IF1 f, A[] l) {
return lambdaMap(f, l);
}
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);
}
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