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.*;
// based on: https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html
// TODO: implement NavigableSet
// RAM use in a CompressedOOPS JVM (bytes per element):
// ~12 when elements are inserted in sorted order
// ~13.7 when elements are inserted in random order
//
// (Obviously more for very small sets.)
import static x30_pkg.x30_util.DynamicObject;
class main {
static class HyperCompactTreeSet extends AbstractSet {
// A symbol table implemented using a left-leaning red-black BST.
// This is the 2-3 version.
// Note: We sometimes cast the nullSentinel to A
// which is technically incorrect but ok because of type erasure.
// May want to fix just to be clean on the source level too.
private static final boolean RED = true;
private static final boolean BLACK = false;
// replacement for null elements
private static final Object nullSentinel = new Object();
// root of the BST (null, Node or sentinelled user object)
// in the latter case it is assumed to be red
private Object root;
int size; // size of tree set
// BST helper node data type
abstract static class Node {
A val; // associated data
Node left() { return null; } // get left subtree
abstract Node setLeft(Node left); // set left subtree - return potentially replaced node
Node right() { return null; } // get right subtree
abstract Node setRight(Node right); // set right subtree - return potentially replaced node
abstract boolean color();
abstract Node convertToBlack();
abstract Node convertToRed();
abstract Node invertColor();
Node convertToColor(boolean color) { return color == RED ? convertToRed() : convertToBlack(); }
abstract boolean isLeaf();
}
// This represents a common case near a red leaf - a black node
// containing a red leaf in the left slot and null in the right slot.
// Combined with the direct storage of black leaf children in NonLeaf,
// this is all we need to get rid of all the leaf overhead. Yay!
static class SpecialNode extends Node {
A leftVal;
SpecialNode(A leftVal, A val) {
this.val = val;
this.leftVal = leftVal;}
boolean color() { return BLACK; }
Node convertToBlack() { return this; }
Node convertToRed() { return newNode(RED, val, left(), right()); }
Node invertColor() { return convertToRed(); }
Node left() {
return newLeaf(RED, leftVal);
}
Node setLeft(Node left) {
// Can we keep the optimized representation? (Probably this
// is never going to be true.)
if (left != null && left.isLeaf() && left.color() == RED)
{ leftVal = left.val; return this; }
else
return newNode(BLACK, val, left, right());
}
Node right() {
return null;
}
Node setRight(Node right) {
if (right == null) return this;
return newNode(color(), val, left(), right);
}
boolean isLeaf() { return false; }
}
abstract static class NonLeaf extends Node {
// either a Node or a (sentinelled) direct user value
Object left, right;
// color of leaf if left is a user value
boolean defaultLeftLeafColor() { return BLACK; }
// color of leaf if right is a user value
boolean defaultRightLeafColor() { return BLACK; }
Node left() {
return left == null ? null
: left instanceof Node ? (Node) left
: newLeaf(defaultLeftLeafColor(), (A) left);
}
void setLeft_noMorph(Node left) {
this.left = left != null && left.isLeaf() && left.color() == defaultLeftLeafColor() ? left.val : left;
}
void setRight_noMorph(Node right) {
this.right = right != null && right.isLeaf() && right.color() == defaultRightLeafColor() ? right.val : right;
}
Node setLeft(Node left) {
if (color() == BLACK && right == null && left != null && left.isLeaf() && left.color() == RED)
return new SpecialNode(left.val, val);
setLeft_noMorph(left);
if (left == null && right() == null) return newLeaf(color(), val);
return this;
}
Node right() {
return right == null ? null
: right instanceof Node ? (Node) right
: newLeaf(defaultRightLeafColor(), (A) right);
}
Node setRight(Node right) {
// Setting right to null may produce either a leaf or a
// special node, so we just go through newNode.
if (right == null && this.right != null)
return newNode(color(), val, left(), null);
// New right is not null, so we compress (if possible) and store it
setRight_noMorph(right);
return this;
}
boolean isLeaf() { return false; }
}
static class BlackNode extends NonLeaf {
BlackNode(A val) {
this.val = val;}
boolean color() { return BLACK; }
Node convertToBlack() { return this; }
Node convertToRed() { return newNode(RED, val, left(), right()); }
Node invertColor() { return convertToRed(); }
}
static class RedNode extends NonLeaf {
RedNode(A val) {
this.val = val;}
boolean color() { return RED; }
Node convertToBlack() { return newNode(BLACK, val, left(), right()); }
Node convertToRed() { return this; }
Node invertColor() { return convertToBlack(); }
}
abstract static class Leaf extends Node {
boolean isLeaf() { return true; }
Node setLeft(Node left) {
return left == null ? this : newNode(color(), val, left, null);
}
Node setRight(Node right) {
return right == null ? this : newNode(color(), val, null, right);
}
}
static class BlackLeaf extends Leaf {
BlackLeaf(A val) {
this.val = val;}
boolean color() { return BLACK; }
Node convertToBlack() { return this; }
Node convertToRed() { return new RedLeaf(val); }
Node invertColor() { return convertToRed(); }
}
static class RedLeaf extends Leaf {
RedLeaf(A val) {
this.val = val;}
boolean color() { return RED; }
Node convertToBlack() { return new BlackLeaf(val); }
Node convertToRed() { return this; }
Node invertColor() { return convertToBlack(); }
}
HyperCompactTreeSet() {}
HyperCompactTreeSet(Collection extends A> cl) { addAll(cl); }
private static Object deSentinel(Object o) {
return o == nullSentinel ? null : o;
}
private static Object sentinel(Object o) {
return o == null ? nullSentinel : o;
}
// returns false on null (algorithm needs this)
static boolean isRed(Node x) {
return x != null && x.color() == RED;
}
static Node newLeaf(boolean color, A val) {
return color == RED ? new RedLeaf(val) : new BlackLeaf(val);
}
static Node newNode(boolean color, A val, Node left, Node right) {
// Make leaf (always a temporary object now)
if (left == null && right == null)
return newLeaf(color, val);
// Make special node
if (color == BLACK
&& right == null
&& left != null && left.isLeaf() && left.color() == RED)
return new SpecialNode(left.val, val);
// Make normal non-leaf
NonLeaf node = color == RED ? new RedNode(val) : new BlackNode(val);
node.setLeft_noMorph(left);
node.setRight_noMorph(right);
return node;
}
public int size() {
return size;
}
public boolean isEmpty() {
return root == null;
}
Node root() {
return root == null ? null
: root instanceof Node ? (Node) root
: newLeaf(RED, (A) root);
}
void setRoot(Node root) {
if (root == null) this.root = null;
else if (root.isLeaf()) this.root = root.val;
else this.root = root;
}
public boolean add(A val) {
val = (A) sentinel(val);
int oldSize = size;
setRoot(put(root(), val).convertToBlack());
return size > oldSize;
}
// insert the value in the subtree rooted at h
private Node put(Node h, A val) {
if (h == null) { ++size; return new RedLeaf(val); }
int cmp = compare_deSentinel(val, h.val);
if (cmp < 0) h = h.setLeft(put(h.left(), val));
else if (cmp > 0) h = h.setRight(put(h.right(), val)) ;
else { /*h.val = val;*/ } // no overwriting
// fix-up any right-leaning links
if (isRed(h.right()) && !isRed(h.left())) h = rotateLeft(h);
if (isRed(h.left()) && isRed(h.left().left())) h = rotateRight(h);
if (isRed(h.left()) && isRed(h.right())) h = flipColors(h);
return h;
}
final int compare_deSentinel(A a, A b) {
return compare((A) deSentinel(a), (A) deSentinel(b));
}
// override me if you wish
int compare(A a, A b) {
return cmp(a, b);
}
public boolean remove(Object key) {
if (root == null || !contains(key)) return false;
key = sentinel(key);
// if both children of root are black, set root to red
Node root = root();
if (!isRed(root.left()) && !isRed(root.right()))
root = root.convertToRed();
root = delete(root, (A) key);
if (root != null) root = root.convertToBlack();
setRoot(root);
// assert check();
return true;
}
// delete the key-value pair with the given key rooted at h
private Node delete(Node h, A key) {
// assert get(h, key) != null;
if (compare_deSentinel(key, h.val) < 0) {
if (!isRed(h.left()) && !isRed(h.left().left()))
h = moveRedLeft(h);
h = h.setLeft(delete(h.left(), key));
}
else {
if (isRed(h.left()))
h = rotateRight(h);
if (compare_deSentinel(key, h.val) == 0 && (h.right() == null)) {
--size; return null;
} if (!isRed(h.right()) && !isRed(h.right().left()))
h = moveRedRight(h);
if (compare_deSentinel(key, h.val) == 0) {
--size;
Node x = min(h.right());
h.val = x.val;
// h.val = get(h.right(), min(h.right()).val);
// h.val = min(h.right()).val;
h = h.setRight(deleteMin(h.right()));
}
else h = h.setRight(delete(h.right(), key));
}
return balance(h);
}
// make a left-leaning link lean to the right
private Node rotateRight(Node h) {
// assert (h != null) && isRed(h.left());
Node x = h.left();
h = h.setLeft(x.right());
x = x.setRight(h);
x = x.convertToColor(x.right().color());
x = x.setRight(x.right().convertToRed());
return x;
}
// make a right-leaning link lean to the left
private Node rotateLeft(Node h) {
// assert (h != null) && isRed(h.right());
Node x = h.right();
h = h.setRight(x.left());
x = x.setLeft(h);
x = x.convertToColor(x.left().color());
x = x.setLeft(x.left().convertToRed());
return x;
}
// flip the colors of a node and its two children
private Node flipColors(Node h) {
// h must have opposite color of its two children
// assert (h != null) && (h.left() != null) && (h.right() != null);
// assert (!isRed(h) && isRed(h.left()) && isRed(h.right()))
// || (isRed(h) && !isRed(h.left()) && !isRed(h.right()));
h = h.setLeft(h.left().invertColor());
h = h.setRight(h.right().invertColor());
return h.invertColor();
}
// Assuming that h is red and both h.left() and h.left().left()
// are black, make h.left() or one of its children red.
private Node moveRedLeft(Node h) {
// assert (h != null);
// assert isRed(h) && !isRed(h.left()) && !isRed(h.left().left());
h = flipColors(h);
if (isRed(h.right().left())) {
h = h.setRight(rotateRight(h.right()));
h = rotateLeft(h);
h = flipColors(h);
}
return h;
}
// Assuming that h is red and both h.right() and h.right().left()
// are black, make h.right() or one of its children red.
private Node moveRedRight(Node h) {
// assert (h != null);
// assert isRed(h) && !isRed(h.right()) && !isRed(h.right().left());
h = flipColors(h);
if (isRed(h.left().left())) {
h = rotateRight(h);
h = flipColors(h);
}
return h;
}
// restore red-black tree invariant
private Node balance(Node h) {
// assert (h != null);
if (isRed(h.right())) h = rotateLeft(h);
if (isRed(h.left()) && isRed(h.left().left())) h = rotateRight(h);
if (isRed(h.left()) && isRed(h.right())) h = flipColors(h);
return h;
}
/**
* Returns the height of the BST (for debugging).
* @return the height of the BST (a 1-node tree has height 0)
*/
public int height() {
return height(root());
}
private int height(Node x) {
if (x == null) return -1;
return 1 + Math.max(height(x.left()), height(x.right()));
}
public boolean contains(Object val) {
return find(root(), (A) sentinel(val)) != null;
}
public A find(A probeVal) {
probeVal = (A) sentinel(probeVal);
Node n = find(root(), probeVal);
return n == null ? null : n.val;
}
// value associated with the given key in subtree rooted at x; null if no such key
private A get(Node x, A key) {
x = find(x, key);
return x == null ? null : x.val;
}
Node find(Node x, A key) {
while (x != null) {
int cmp = compare_deSentinel(key, x.val);
if (cmp < 0) x = x.left();
else if (cmp > 0) x = x.right();
else return x;
}
return null;
}
private boolean check() {
if (!is23()) println("Not a 2-3 tree");
if (!isBalanced()) println("Not balanced");
return is23() && isBalanced();
}
// Does the tree have no red right links, and at most one (left)
// red links in a row on any path?
private boolean is23() { return is23(root()); }
private boolean is23(Node x) {
if (x == null) return true;
if (isRed(x.right())) return false;
if (x != root && isRed(x) && isRed(x.left())) return false;
return is23(x.left()) && is23(x.right());
}
// do all paths from root to leaf have same number of black edges?
private boolean isBalanced() {
int black = 0; // number of black links on path from root to min
Node x = root();
while (x != null) {
if (!isRed(x)) black++;
x = x.left();
}
return isBalanced(root(), black);
}
// does every path from the root to a leaf have the given number of black links?
private boolean isBalanced(Node x, int black) {
if (x == null) return black == 0;
if (!isRed(x)) black--;
return isBalanced(x.left(), black) && isBalanced(x.right(), black);
}
public void clear() { root = null; size = 0; }
// the smallest key in subtree rooted at x; null if no such key
private Node min(Node x) {
// assert x != null;
while (x.left() != null) x = x.left();
return x;
}
private Node deleteMin(Node h) {
if (h.left() == null)
return null;
if (!isRed(h.left()) && !isRed(h.left().left()))
h = moveRedLeft(h);
h = h.setLeft(deleteMin(h.left()));
return balance(h);
}
public Iterator iterator() {
return new MyIterator();
}
class MyIterator extends IterableIterator {
List> path = new ArrayList();
MyIterator() {
fetch(root());
}
void fetch(Node node) {
while (node != null) {
path.add(node);
node = node.left();
}
}
public boolean hasNext() { return !path.isEmpty(); }
public A next() {
if (path.isEmpty()) throw fail("no more elements");
Node node = popLast(path);
// last node is always a leaf, so left is null
// so proceed to fetch right branch
fetch(node.right());
return (A) deSentinel(node.val);
}
}
// Returns the smallest key in the symbol table greater than or equal to {@code key}.
public A ceiling(A key) {
key = (A) sentinel(key);
Node x = ceiling(root(), key);
return x == null ? null : x.val;
}
// the smallest key in the subtree rooted at x greater than or equal to the given key
Node ceiling(Node x, A key) {
if (x == null) return null;
int cmp = compare_deSentinel(key, x.val);
if (cmp == 0) return x;
if (cmp > 0) return ceiling(x.right(), key);
Node t = ceiling(x.left(), key);
if (t != null) return t;
else return x;
}
public A floor(A key) {
key = (A) sentinel(key);
Node x = floor(root(), key);
return x == null ? null : x.val;
}
// the largest key in the subtree rooted at x less than or equal to the given key
Node floor(Node x, A key) {
if (x == null) return null;
int cmp = compare_deSentinel(key, x.val);
if (cmp == 0) return x;
if (cmp < 0) return floor(x.left(), key);
Node t = floor(x.right(), key);
if (t != null) return t;
else return x;
}
void testInternalStructure() {
// one leaf object (root) is allowed - could even optimize that
assertTrue(countLeafObjects() <= 1);
}
// count leaf objects we didn't optimize away
int countLeafObjects() { return countLeafObjects(root()); }
int countLeafObjects(Node node) {
if (node instanceof Leaf) return 1;
if (node instanceof NonLeaf)
return countLeafObjects(optCast(Node.class, ((NonLeaf) node).left))
+ countLeafObjects(optCast(Node.class, ((NonLeaf) node).right));
return 0;
}
Collection unoptimizedNodes() {
List out = new ArrayList();
findUnoptimizedNodes(out);
return out;
}
void findUnoptimizedNodes(List out) { findUnoptimizedNodes(root(), out); }
void findUnoptimizedNodes(Node node, List out) {
if (node == null) return;
if (node instanceof NonLeaf) {
if (isUnoptimizedNode((NonLeaf) node)) out.add((NonLeaf) node);
findUnoptimizedNodes(optCast(Node.class, ((NonLeaf) node).left), out);
findUnoptimizedNodes(optCast(Node.class, ((NonLeaf) node).right), out);
}
}
boolean isUnoptimizedNode(Node node) {
if (node instanceof NonLeaf)
return ((NonLeaf) node).left instanceof Leaf
|| ((NonLeaf) node).right instanceof Leaf;
return false;
}
// Compact me (minimize space use). Returns a compacted copy.
// This only has an effect when elements were inserted in non-sorted
// or and/or elements were removed.
HyperCompactTreeSet compact() {
return new HyperCompactTreeSet(this);
}
}
static void addAll(Collection c, Iterable b) {
if (c != null && b != null) for (A a : b) c.add(a);
}
static boolean addAll(Collection c, Collection b) {
return c != null && b != null && c.addAll(b);
}
static boolean addAll(Collection c, B... b) {
return c != null && b != null && c.addAll(Arrays.asList(b));
}
static Map addAll(Map a, Map extends A,? extends B> b) {
if (a != null && b != null) a.putAll(b);
return a;
}
static void put(Map map, A a, B b) {
if (map != null) map.put(a, b);
}
static void put(List l, int i, A a) {
if (l != null && i >= 0 && i < l(l)) l.set(i, a);
}
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);
}
static boolean contains(Collection c, Object o) {
return c != null && c.contains(o);
}
static boolean contains(Object[] x, Object o) {
if (x != null)
for (Object a : x)
if (eq(a, o))
return true;
return false;
}
static boolean contains(String s, char c) {
return s != null && s.indexOf(c) >= 0;
}
static boolean contains(String s, String b) {
return s != null && s.indexOf(b) >= 0;
}
static boolean contains(BitSet bs, int i) {
return bs != null && bs.get(i);
}
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 String find(String pattern, String text) {
Matcher matcher = Pattern.compile(pattern).matcher(text);
if (matcher.find())
return matcher.group(1);
return null;
}
static A find(Collection c, Object... data) {
for (A x : c)
if (checkFields(x, data))
return x;
return null;
}
static A println(A a) {
return print(a);
}
static Iterator iterator(Iterable c) {
return c == null ? emptyIterator() : c.iterator();
}
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 A popLast(List l) {
return liftLast(l);
}
static List popLast(int n, List l) {
return liftLast(n, l);
}
static double floor(double d) {
return Math.floor(d);
}
static void assertTrue(Object o) {
if (!(eq(o, true) /*|| isTrue(pcallF(o))*/))
throw fail(str(o));
}
static boolean assertTrue(String msg, boolean b) {
if (!b)
throw fail(msg);
return b;
}
static boolean assertTrue(boolean b) {
if (!b)
throw fail("oops");
return b;
}
static A optCast(Class c, Object o) {
return isInstance(c, o) ? (A) o : 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(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 boolean eq(Object a, Object b) {
return a == b || a != null && b != null && a.equals(b);
}
// a little kludge for stuff like eq(symbol, "$X")
static boolean eq(Symbol a, String b) {
return eq(str(a), b);
}
static boolean checkFields(Object x, Object... data) {
for (int i = 0; i < l(data); i += 2)
if (neq(getOpt(x, (String) data[i]), data[i+1]))
return false;
return true;
}
static volatile StringBuffer local_log = new StringBuffer(); // not redirected
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