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_v2 extends VStack implements IBStack {
static int idCounter;
int stackID = ++idCounter; // for debugging
// cloned version made at last branch point
BStack_v2 snapshot;
// remaining options at last branch point
Iterator options;
// steps to undo before switching to the alternative
List undos;
BStack_v2() {}
BStack_v2(Computable computation) { push(computation); }
BStack_v2(Iterable l) { pushAll(l); }
static class NoOptionsException extends RuntimeException {}
BStack_v2 cloneStack() {
BStack_v2 s = new BStack_v2();
s.snapshot = snapshot;
s.options = options;
s.undos = undos;
undos = null;
s.stack = shallowCloneElements(stack);
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);
}
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 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_v2 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_v2 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_v2();
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;
}
}
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);
}
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 String shortClassName_dropNumberPrefix(Object o) {
return dropNumberPrefix(shortClassName(o));
}
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 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 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 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 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 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