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.*; class main { static DoublePt addDoublePts(DoublePt a, DoublePt b) { return a == null ? b : b == null ? a : doublePt(a.x_double()+b.x_double(), a.y_double()+b.y_double()); } static IDoublePt addDoublePts(IDoublePt a, IDoublePt b) { return a == null ? b : b == null ? a : doublePt(a.x_double()+b.x_double(), a.y_double()+b.y_double()); } static DoublePt doublePt(double x) { return doublePt(x, x); } static DoublePt doublePt(double x, double y) { return new DoublePt(x, y); } 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; } } interface IDoublePt { public double x_double(); public double y_double(); } 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); } }