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.*;
// adapted for Java from https://codepen.io/tculda/pen/pogwpOw
import java.awt.geom.*;

class main {

  static class MultiPointGradient implements MakesBufferedImage {

    List<Pair<DoublePt, Color>> gradientPoints;

    int w, h;

    int[] pixels;

    double[] gradientPointArray;

    Color[] colors;

    boolean hasRun = false;

    MultiPointGradient(List<Pair<DoublePt, Color>> gradientPoints, int w, int h) {
      this.h = h;
      this.w = w;
      this.gradientPoints = gradientPoints;
    }

    MultiPointGradient(int w, int h, List<Pair<DoublePt, Color>> gradientPoints) {
      this.gradientPoints = gradientPoints;
      this.h = h;
      this.w = w;
    }

    public int getWidth() {
      return w;
    }

    public int getHeight() {
      return h;
    }

    public BufferedImage getBufferedImage() {
      this.run();
      return intArrayToBufferedImageWithoutAlpha(pixels, w, h);
    }

    void init() {
      if (pixels == null)
        pixels = new int[w * h];
      if (gradientPointArray == null)
        gradientPointArray = doublePtsToDoubleArray(pairsA(gradientPoints));
      if (colors == null)
        colors = toArray(Color.class, pairsB(gradientPoints));
    }

    public void run() {
      try {
        if (hasRun)
          return;
        hasRun = true;
        init();
        int n = l(colors);
        double[] colorRatios = new double[n];
        int iPixel = 0;
        for (int y = 0; y < h; y++) for (int x = 0; x < w; x++) {
          fillArray(colorRatios, 1);
          for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j) {
            var d = getProjectionDistance2(gradientPointArray[i * 2], gradientPointArray[i * 2 + 1], gradientPointArray[j * 2], gradientPointArray[j * 2 + 1], x, y);
            colorRatios[i] *= clampZeroToOne(d);
          }
          pixels[iPixel++] = blendMultipleColorsToInt(colors, colorRatios);
        }
      } catch (Exception __e) {
        throw rethrow(__e);
      }
    }
  }

  // from: https://stackoverflow.com/questions/14416107/int-array-to-bufferedimage
  // pixels are RGB pixels
  static BufferedImage intArrayToBufferedImageWithoutAlpha(int[] pixels, int w, int h) {
    int[] bitMasks = { 0xFF0000, 0xFF00, 0xFF };
    SinglePixelPackedSampleModel sm = new SinglePixelPackedSampleModel(DataBuffer.TYPE_INT, w, h, bitMasks);
    DataBufferInt db = new DataBufferInt(pixels, pixels.length);
    WritableRaster wr = Raster.createWritableRaster(sm, db, new Point());
    DirectColorModel cm = new DirectColorModel(24, bitMasks[0], bitMasks[1], bitMasks[2], 0);
    return new BufferedImage(cm, wr, false, null);
  }

  static double[] doublePtsToDoubleArray(List<DoublePt> l) {
    int n = l(l);
    double[] array = new double[n * 2];
    for (int i = 0; i < l(l); i++) {
      var p = l.get(i);
      array[i * 2] = p.x;
      array[i * 2 + 1] = p.y;
    }
    return array;
  }

  static <A, B> List<A> pairsA(Collection<Pair<A, B>> l) {
    return firstOfPairs(l);
  }

  static Object[] toArray(Collection c) {
    return toObjectArray(c);
  }

  static <A> A[] toArray(Class<A> type, Iterable<A> c) {
    return toArray(c, type);
  }

  static <A> A[] toArray(Class<A> type, Collection<A> c) {
    return toArray(c, type);
  }

  static <A> A[] toArray(Collection<A> c, Class<A> type) {
    A[] a = arrayOfType(l(c), type);
    if (a.length == 0)
      return a;
    asList(c).toArray(a);
    return a;
  }

  static <A> A[] toArray(Iterable<A> c, Class<A> type) {
    var c2 = asList(c);
    A[] a = arrayOfType(l(c2), type);
    if (a.length == 0)
      return a;
    c2.toArray(a);
    return a;
  }

  // array must have correct length and will be filled
  static <A> A[] toArray(A[] array, Collection c) {
    if (array == null || c == null)
      return null;
    asList(c).toArray(array);
    return array;
  }

  static <A, B> List<B> pairsB(Collection<Pair<A, B>> l) {
    return secondOfPairs(l);
  }

  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();
  }

  // consumes the iterator && closes it if possible
  static int l(Iterator i) {
    return iteratorCount_int_close(i);
  }

  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 void fillArray(byte[] a, byte value) {
    Arrays.fill(a, value);
  }

  static void fillArray(int[] a, int value) {
    Arrays.fill(a, value);
  }

  static void fillArray(float[] a, float value) {
    Arrays.fill(a, value);
  }

  static void fillArray(double[] a, double value) {
    Arrays.fill(a, value);
  }

  // from https://codepen.io/tculda/pen/pogwpOw
  // (https://stackoverflow.com/questions/22356012/multiple-points-colors-gradient-on-html5-canvas)
  static double getProjectionDistance2(DoublePt a, DoublePt b, DoublePt c) {
    return getProjectionDistance2(a.x, a.y, b.x, b.y, c.x, c.y);
  }

  static double getProjectionDistance2(double ax, double ay, double bx, double by, double cx, double cy) {
    var k2 = bx * bx - bx * ax + by * by - by * ay;
    var k1 = ax * ax - bx * ax + ay * ay - by * ay;
    var ab2 = (ax - bx) * (ax - bx) + (ay - by) * (ay - by);
    var kcom = (cx * (ax - bx) + cy * (ay - by));
    var d2 = (k2 + kcom) / ab2;
    return d2;
  }

  static float clampZeroToOne(float x) {
    return x < 0 ? 0 : x > 1 ? 1 : x;
  }

  static double clampZeroToOne(double x) {
    return x < 0 ? 0 : x > 1 ? 1 : x;
  }

  static int blendMultipleColorsToInt(List<Pair<Color, Double>> colors) {
    double sum = doubleSum(pairsB(colors));
    double r = 0, g = 0, b = 0;
    for (var __0 : colors) {
      var color = pairA(__0);
      var weight = pairB(__0);
      r += color.getRed() * weight;
      g += color.getGreen() * weight;
      b += color.getBlue() * weight;
    }
    return rgbInt(roundedRatio(r, sum), roundedRatio(g, sum), roundedRatio(b, sum));
  }

  static int blendMultipleColorsToInt(Color[] colors, double[] weights) {
    double sum = doubleSum(weights);
    double r = 0, g = 0, b = 0;
    for (int i = 0; i < l(colors); i++) {
      Color color = colors[i];
      double weight = weights[i];
      r += color.getRed() * weight;
      g += color.getGreen() * weight;
      b += color.getBlue() * weight;
    }
    return rgbInt(roundedRatio(r, sum), roundedRatio(g, sum), roundedRatio(b, sum));
  }

  static RuntimeException rethrow(Throwable t) {
    throw t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
  }

  static RuntimeException rethrow(String msg, Throwable t) {
    throw new RuntimeException(msg, t);
  }

  static <A, B> List<A> firstOfPairs(Collection<Pair<A, B>> l) {
    List<A> out = new ArrayList();
    for (Pair<A, B> p : unnull(l)) out.add(firstOfPair(p));
    return out;
  }

  // binary legacy signature
  static Object[] toObjectArray(Collection c) {
    return toObjectArray((Iterable) c);
  }

  static Object[] toObjectArray(Iterable c) {
    List l = asList(c);
    return l.toArray(new Object[l.size()]);
  }

  static <A> A[] arrayOfType(Class<A> type, int n) {
    return makeArray(type, n);
  }

  static <A> A[] arrayOfType(int n, Class<A> type) {
    return arrayOfType(type, n);
  }

  // unclear semantics as to whether return null on null
  static <A> ArrayList<A> asList(A[] a) {
    return a == null ? new ArrayList<A>() : new ArrayList<A>(Arrays.asList(a));
  }

  static ArrayList<Integer> asList(int[] a) {
    if (a == null)
      return null;
    ArrayList<Integer> l = emptyList(a.length);
    for (int i : a) l.add(i);
    return l;
  }

  static ArrayList<Long> asList(long[] a) {
    if (a == null)
      return null;
    ArrayList<Long> l = emptyList(a.length);
    for (long i : a) l.add(i);
    return l;
  }

  static ArrayList<Float> asList(float[] a) {
    if (a == null)
      return null;
    ArrayList<Float> l = emptyList(a.length);
    for (float i : a) l.add(i);
    return l;
  }

  static ArrayList<Double> asList(double[] a) {
    if (a == null)
      return null;
    ArrayList<Double> l = emptyList(a.length);
    for (double i : a) l.add(i);
    return l;
  }

  static ArrayList<Short> asList(short[] a) {
    if (a == null)
      return null;
    ArrayList<Short> l = emptyList(a.length);
    for (short i : a) l.add(i);
    return l;
  }

  static <A> ArrayList<A> asList(Iterator<A> it) {
    ArrayList l = new ArrayList();
    if (it != null)
      while (it.hasNext()) l.add(it.next());
    return l;
  }

  // disambiguation
  static <A> ArrayList<A> asList(IterableIterator<A> s) {
    return asList((Iterator) s);
  }

  static <A> ArrayList<A> asList(Iterable<A> 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 <A> ArrayList<A> asList(Enumeration<A> e) {
    ArrayList l = new ArrayList();
    if (e != null)
      while (e.hasMoreElements()) l.add(e.nextElement());
    return l;
  }

  static <A> List<A> asList(Pair<A, A> p) {
    return p == null ? null : ll(p.a, p.b);
  }

  static <A, B> List<B> secondOfPairs(Collection<Pair<A, B>> l) {
    return lambdaMap(__15 -> secondOfPair(__15), l);
  }

  static <A> int iteratorCount_int_close(Iterator<A> 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 double doubleSum(Iterable<Double> l) {
    double sum = 0;
    for (Double i : unnull(l)) if (i != null)
      sum += i;
    return sum;
  }

  static double doubleSum(double... l) {
    double sum = 0;
    if (l != null)
      for (double i : l) sum += i;
    return sum;
  }

  static <A, B> A pairA(Pair<A, B> p) {
    return p == null ? null : p.a;
  }

  static <A, B> B pairB(Pair<A, B> p) {
    return p == null ? null : p.b;
  }

  static int rgbInt(int r, int g, int b) {
    return (clamp(r, 0, 255) << 16) | (clamp(g, 0, 255) << 8) | clamp(b, 0, 255);
  }

  static int roundedRatio(double a, double b) {
    return iround(ratio(a, b));
  }

  static int roundedRatio(int a, int b) {
    return (a + b / 2 - 1) / b;
  }

  static String unnull(String s) {
    return s == null ? "" : s;
  }

  static <A> Collection<A> unnull(Collection<A> l) {
    return l == null ? emptyList() : l;
  }

  static <A> List<A> unnull(List<A> l) {
    return l == null ? emptyList() : l;
  }

  static int[] unnull(int[] l) {
    return l == null ? emptyIntArray() : l;
  }

  static char[] unnull(char[] l) {
    return l == null ? emptyCharArray() : l;
  }

  static double[] unnull(double[] l) {
    return l == null ? emptyDoubleArray() : l;
  }

  static <A, B> Map<A, B> unnull(Map<A, B> l) {
    return l == null ? emptyMap() : l;
  }

  static <A> Iterable<A> unnull(Iterable<A> i) {
    return i == null ? emptyList() : i;
  }

  static <A> A[] unnull(A[] a) {
    return a == null ? (A[]) emptyObjectArray() : a;
  }

  static BitSet unnull(BitSet b) {
    return b == null ? new BitSet() : b;
  }

  static Pt unnull(Pt p) {
    return p == null ? new Pt() : p;
  }

  // ifclass Symbol
  static <A, B> Pair<A, B> unnull(Pair<A, B> p) {
    return p != null ? p : new Pair(null, null);
  }

  static int unnull(Integer i) {
    return i == null ? 0 : i;
  }

  static long unnull(Long l) {
    return l == null ? 0L : l;
  }

  static double unnull(Double l) {
    return l == null ? 0.0 : l;
  }

  static <A, B> A firstOfPair(Pair<A, B> p) {
    return p == null ? null : p.a;
  }

  static <A> A[] makeArray(Class<A> type, int n) {
    return (A[]) Array.newInstance(type, n);
  }

  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 <A> ArrayList<A> emptyList(Class<A> c) {
    return new ArrayList();
  }

  static <A> List<A> ll(A... a) {
    ArrayList l = new ArrayList(a.length);
    if (a != null)
      for (A x : a) l.add(x);
    return l;
  }

  static <A, B> List<B> lambdaMap(IF1<A, B> f, Iterable<A> l) {
    return map(l, f);
  }

  static <A, B> List<B> lambdaMap(IF1<A, B> f, A[] l) {
    return map(l, f);
  }

  static <A, B> B secondOfPair(Pair<A, B> p) {
    return p == null ? null : p.b;
  }

  static float clamp(float x, float a, float b) {
    return x < a ? a : x > b ? b : x;
  }

  static double clamp(double x, double a, double b) {
    return x < a ? a : x > b ? b : x;
  }

  static int clamp(int x, int a, int b) {
    return x < a ? a : x > b ? b : x;
  }

  static long clamp(long x, long a, long b) {
    return x < a ? a : x > b ? b : x;
  }

  static int iround(double d) {
    return (int) Math.round(d);
  }

  static int iround(Number n) {
    return iround(toDouble(n));
  }

  static long ratio(long x, long y) {
    return y == 0 ? 0 : x / y;
  }

  static double ratio(double x, double y) {
    return y == 0 ? 0 : x / y;
  }

  static int[] emptyIntArray_a = new int[0];

  static int[] emptyIntArray() {
    return emptyIntArray_a;
  }

  static char[] emptyCharArray = new char[0];

  static char[] emptyCharArray() {
    return emptyCharArray;
  }

  static double[] emptyDoubleArray = new double[0];

  static double[] emptyDoubleArray() {
    return emptyDoubleArray;
  }

  static Map emptyMap() {
    return new HashMap();
  }

  static Object[] emptyObjectArray_a = new Object[0];

  static Object[] emptyObjectArray() {
    return emptyObjectArray_a;
  }

  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<Integer> 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 <A extends Comparable<A>> A max(A a, A b) {
    return cmp(a, b) >= 0 ? a : b;
  }

  static <A, B> List<B> map(IF1<A, B> f, Iterable<A> l) {
    return map(l, f);
  }

  static <A, B> List<B> map(Iterable<A> l, IF1<A, B> f) {
    List x = emptyList(l);
    if (l != null)
      for (A o : l) {
        ping();
        x.add(f.get(o));
      }
    return x;
  }

  static <A, B> List<B> map(IF1<A, B> f, A[] l) {
    return map(l, f);
  }

  static <A, B> List<B> map(A[] l, IF1<A, B> f) {
    List x = emptyList(l);
    if (l != null)
      for (A o : l) {
        ping();
        x.add(f.get(o));
      }
    return x;
  }

  static <A, B, C> List<C> map(Map<A, B> map, IF2<A, B, C> f) {
    List x = new ArrayList();
    if (map != null)
      for (Map.Entry<A, B> e : map.entrySet()) {
        ping();
        x.add(f.get(e.getKey(), e.getValue()));
      }
    return x;
  }

  // new magic alias for mapLL - does it conflict?
  static <A, B> List<A> map(IF1<A, B> f, A data1, A... moreData) {
    List x = emptyList(l(moreData) + 1);
    x.add(f.get(data1));
    if (moreData != null)
      for (A o : moreData) {
        ping();
        x.add(f.get(o));
      }
    return x;
  }

  static double toDouble(Object o) {
    if (o instanceof Number)
      return ((Number) o).doubleValue();
    if (o instanceof BigInteger)
      return ((BigInteger) o).doubleValue();
    if (o instanceof String)
      return parseDouble((String) o);
    if (o == null)
      return 0.0;
    throw fail(o);
  }

  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);
  }

  // you can change this function to allow interrupting long calculations from the outside. just throw a RuntimeException.
  static boolean ping() {
    return true;
  }

  static boolean ping_impl(boolean okInCleanUp) {
    return true;
  }

  static <A, B> B callF(IF1<A, B> f, A a) {
    return f == null ? null : f.get(a);
  }

  static <A, B> B callF(A a, IF1<A, B> f) {
    return f == null ? null : f.get(a);
  }

  static <A, B, C> C callF(IF2<A, B, C> f, A a, B b) {
    return f == null ? null : f.get(a, b);
  }

  static <A> void callF(A a, IVF1<A> f) {
    if (f != null)
      f.get(a);
  }

  static <A> void callF(IVF1<A> f, A a) {
    if (f != null)
      f.get(a);
  }

  static Object callF(Runnable r) {
    {
      if (r != null)
        r.run();
    }
    return null;
  }

  static double parseDouble(String s) {
    return empty(s) ? 0.0 : Double.parseDouble(s);
  }

  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 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(File f) {
    return getFileSize(f) == 0;
  }

  static boolean empty(Rect r) {
    return !(r != null && r.w != 0 && r.h != 0);
  }

  static RuntimeException asRuntimeException(Throwable t) {
    return t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
  }

  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 String getClassName(Object o) {
    return o == null ? "null" : o instanceof Class ? ((Class) o).getName() : o.getClass().getName();
  }

  static interface IF2<A, B, C> {

    C get(A a, B b);
  }

  static interface IF1<A, B> {

    B get(A a);
  }

  static class DoublePt implements IDoublePt {

    double x, y;

    DoublePt() {
    }

    DoublePt(Point p) {
      x = p.x;
      y = p.y;
    }

    DoublePt(double x, double y) {
      this.y = y;
      this.x = x;
    }

    public boolean equals(Object p) {
      if (p instanceof DoublePt) {
        return x == ((DoublePt) p).x && y == ((DoublePt) p).y;
      }
      return false;
    }

    public int hashCode() {
      return boostHashCombine(main.hashCode(x), main.hashCode(y));
    }

    public String toString() {
      return x + ", " + y;
    }

    double length() {
      return sqrt(x * x + y * y);
    }

    public double x_double() {
      return x;
    }

    public double y_double() {
      return y;
    }
  }

  static interface IVF1<A> {

    void get(A a);
  }

  // you still need to implement hasNext() and next()
  static abstract class IterableIterator<A> implements Iterator<A>, Iterable<A> {

    public Iterator<A> iterator() {
      return this;
    }

    public void remove() {
      unsupportedOperation();
    }
  }

  static interface MakesBufferedImage extends WidthAndHeight {

    BufferedImage getBufferedImage();

    public default void drawAt(Graphics2D g, int x, int y) {
      g.drawImage(getBufferedImage(), x, y, null);
    }
  }

  static class Pair<A, B> implements Comparable<Pair<A, B>> {

    A a;

    B b;

    Pair() {
    }

    Pair(A a, B b) {
      this.b = b;
      this.a = a;
    }

    public int hashCode() {
      return hashCodeFor(a) + 2 * hashCodeFor(b);
    }

    public boolean equals(Object o) {
      if (o == this)
        return true;
      if (!(o instanceof Pair))
        return false;
      Pair t = (Pair) o;
      return eq(a, t.a) && eq(b, t.b);
    }

    public String toString() {
      return "<" + a + ", " + b + ">";
    }

    public int compareTo(Pair<A, B> p) {
      if (p == null)
        return 1;
      int i = ((Comparable<A>) a).compareTo(p.a);
      if (i != 0)
        return i;
      return ((Comparable<B>) b).compareTo(p.b);
    }
  }

  static class Fail extends RuntimeException implements IFieldsToList {

    Object[] objects;

    Fail() {
    }

    Fail(Object... objects) {
      this.objects = objects;
    }

    public Object[] _fieldsToList() {
      return new Object[] { objects };
    }

    Fail(Throwable cause, Object... objects) {
      super(cause);
      this.objects = objects;
    }

    public String toString() {
      return joinNemptiesWithColon("Fail", commaCombine(getCause(), objects));
    }
  }

  static interface IFieldsToList {

    Object[] _fieldsToList();
  }

  interface IDoublePt {

    public double x_double();

    public double y_double();
  }

  static interface WidthAndHeight {

    default int w() {
      return getWidth();
    }

    int getWidth();

    default int h() {
      return getHeight();
    }

    int getHeight();

    public default Rect bounds() {
      return rect(0, 0, getWidth(), getHeight());
    }
  }

  final static class Rect implements IFieldsToList {

    static final String _fieldOrder = "x y w h";

    int x;

    int y;

    int w;

    int h;

    Rect() {
    }

    Rect(int x, int y, int w, int h) {
      this.h = h;
      this.w = w;
      this.y = y;
      this.x = x;
    }

    public boolean equals(Object o) {
      if (!(o instanceof Rect))
        return false;
      Rect __1 = (Rect) o;
      return x == __1.x && y == __1.y && w == __1.w && h == __1.h;
    }

    public int hashCode() {
      int h = 2543108;
      h = boostHashCombine(h, _hashCode(x));
      h = boostHashCombine(h, _hashCode(y));
      h = boostHashCombine(h, _hashCode(w));
      h = boostHashCombine(h, _hashCode(h));
      return h;
    }

    public Object[] _fieldsToList() {
      return new Object[] { x, y, w, h };
    }

    Rect(Rectangle r) {
      x = r.x;
      y = r.y;
      w = r.width;
      h = r.height;
    }

    Rect(Pt p, int w, int h) {
      this.h = h;
      this.w = w;
      x = p.x;
      y = p.y;
    }

    Rect(Rect r) {
      x = r.x;
      y = r.y;
      w = r.w;
      h = r.h;
    }

    Rectangle getRectangle() {
      return new Rectangle(x, y, w, h);
    }

    public String toString() {
      return x + "," + y + " / " + w + "," + h;
    }

    int x1() {
      return x;
    }

    int y1() {
      return y;
    }

    int x2() {
      return x + w;
    }

    int y2() {
      return y + h;
    }

    boolean contains(Pt p) {
      return contains(p.x, p.y);
    }

    boolean contains(int _x, int _y) {
      return _x >= x && _y >= y && _x < x + w && _y < y + h;
    }

    boolean contains(Rectangle r) {
      return rectContains(this, r);
    }

    boolean empty() {
      return w <= 0 || h <= 0;
    }

    int getWidth() {
      return w;
    }

    int getHeight() {
      return h;
    }
  }

  static class Pt implements Comparable<Pt>, IDoublePt {

    int x, y;

    Pt() {
    }

    Pt(Point p) {
      x = p.x;
      y = p.y;
    }

    Pt(int x, int y) {
      this.y = y;
      this.x = x;
    }

    Point getPoint() {
      return new Point(x, y);
    }

    public boolean equals(Object o) {
      return o instanceof Pt && x == ((Pt) o).x && y == ((Pt) o).y;
    }

    public int hashCode() {
      return boostHashCombine(x, y);
    }

    // compare in scan order
    public int compareTo(Pt p) {
      if (y != p.y)
        return cmp(y, p.y);
      return cmp(x, p.x);
    }

    public String toString() {
      return x + ", " + y;
    }

    double length() {
      return sqrt(x * x + y * y);
    }

    public Pt minus(Pt p) {
      return ptMinus(this, p);
    }

    public double x_double() {
      return x;
    }

    public double y_double() {
      return y;
    }
  }

  static int boostHashCombine(int a, int b) {
    return a ^ (b + 0x9e3779b9 + (a << 6) + (a >>> 2));
  // OLD (changed) 2022/3/10: ret a ^ (b + 0x9e3779b9 + (a << 6) + (a >> 2));
  }

  static int hashCode(Object a) {
    return a == null ? 0 : a.hashCode();
  }

  static int hashCode(long l) {
    return Long.hashCode(l);
  }

  static int hashCode(double d) {
    return Double.hashCode(d);
  }

  static double sqrt(double x) {
    return Math.sqrt(x);
  }

  static <A> Iterator<A> iterator(Iterable<A> c) {
    return c == null ? emptyIterator() : c.iterator();
  }

  static UnsupportedOperationException unsupportedOperation() {
    throw new UnsupportedOperationException();
  }

  static int hashCodeFor(Object a) {
    return a == null ? 0 : a.hashCode();
  }

  static boolean eq(Object a, Object b) {
    return a == b || a != null && b != null && a.equals(b);
  }

  static String joinNemptiesWithColon(String... strings) {
    return joinNempties(": ", strings);
  }

  static String joinNemptiesWithColon(Collection<String> strings) {
    return joinNempties(": ", strings);
  }

  static String commaCombine(Object... l) {
    return joinNemptiesWithComma(flattenCollectionsAndArrays(ll(l)));
  }

  static Rect rect(int x, int y, int w, int h) {
    return new Rect(x, y, w, h);
  }

  static Rect rect(Pt p, int w, int h) {
    return new Rect(p.x, p.y, w, h);
  }

  static Rect rect(int w, int h) {
    return new Rect(0, 0, w, h);
  }

  static int _hashCode(Object a) {
    return a == null ? 0 : a.hashCode();
  }

  static boolean contains(Collection c, Object o) {
    return c != null && c.contains(o);
  }

  static boolean contains(Iterable it, Object a) {
    if (it != null)
      for (Object o : it) if (eq(a, o))
        return true;
    return false;
  }

  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 boolean contains(Rect r, Pt p) {
    return rectContains(r, p);
  }

  static boolean rectContains(int x1, int y1, int w, int h, Pt p) {
    return p.x >= x1 && p.y >= y1 && p.x < x1 + w && p.y < y1 + h;
  }

  static boolean rectContains(Rect a, Rect b) {
    return b.x >= a.x && b.y >= a.y && b.x2() <= a.x2() && b.y2() <= a.y2();
  }

  static boolean rectContains(Rect a, Rectangle b) {
    return rectContains(a, toRect(b));
  }

  static boolean rectContains(Rect a, int x, int y) {
    return a != null && a.contains(x, y);
  }

  static boolean rectContains(Rect a, Pt p) {
    return a != null && p != null && a.contains(p);
  }

  static Pt ptMinus(Pt a, Pt b) {
    if (b == null)
      return a;
    return new Pt(a.x - b.x, a.y - b.y);
  }

  static Iterator emptyIterator() {
    return Collections.emptyIterator();
  }

  static String str(Object o) {
    return o == null ? "null" : o.toString();
  }

  static String str(char[] c) {
    return new String(c);
  }

  static String str(char[] c, int offset, int count) {
    return new String(c, offset, count);
  }

  static String joinNempties(String sep, Object... strings) {
    return joinStrings(sep, strings);
  }

  static String joinNempties(String sep, Iterable strings) {
    return joinStrings(sep, strings);
  }

  static String joinNemptiesWithComma(Object... strings) {
    return joinNempties(", ", strings);
  }

  static String joinNemptiesWithComma(Iterable strings) {
    return joinNempties(", ", strings);
  }

  static List flattenCollectionsAndArrays(Iterable a) {
    List l = new ArrayList();
    for (Object x : a) if (x instanceof Collection)
      l.addAll(flattenCollectionsAndArrays((Collection) x));
    else if (x instanceof Object[])
      l.addAll(flattenCollectionsAndArrays(asList((Object[]) x)));
    else
      l.add(x);
    return l;
  }

  static Rect toRect(Rectangle r) {
    return r == null ? null : new Rect(r);
  }

  static Rect toRect(RectangularShape r) {
    return r == null ? null : toRect(r.getBounds());
  }

  static Rect toRect(Rect r) {
    return r;
  }

  static String joinStrings(String sep, Object... strings) {
    return joinStrings(sep, Arrays.asList(strings));
  }

  static String joinStrings(String sep, Iterable strings) {
    StringBuilder buf = new StringBuilder();
    for (Object o : unnull(strings)) {
      String s = strOrNull(o);
      if (nempty(s)) {
        if (nempty(buf))
          buf.append(sep);
        buf.append(s);
      }
    }
    return str(buf);
  }

  static String strOrNull(Object o) {
    return o == null ? null : str(o);
  }

  static boolean nempty(Collection c) {
    return !empty(c);
  }

  static boolean nempty(CharSequence s) {
    return !empty(s);
  }

  static boolean nempty(Object[] o) {
    return !empty(o);
  }

  static boolean nempty(byte[] o) {
    return !empty(o);
  }

  static boolean nempty(int[] o) {
    return !empty(o);
  }

  static boolean nempty(BitSet bs) {
    return !empty(bs);
  }

  static boolean nempty(Map m) {
    return !empty(m);
  }

  static boolean nempty(Iterator i) {
    return i != null && i.hasNext();
  }

  static boolean nempty(Object o) {
    return !empty(o);
  }

  static boolean nempty(Rect r) {
    return r != null && r.w != 0 && r.h != 0;
  }
}
// Include for exporting Java code